Submission #3727415

---

Source Code Expand

#include<bits/stdc++.h>

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
typedef struct aaaaa{
  int x,y,t;
}Grid;
using namespace std;
typedef struct E{
  int to,cost;
}edge;
const int MAX_V=2555;
const int Inf=1e9;
vector<vector<edge> >E(MAX_V);
int d[MAX_V][MAX_V];
void dijkstra(int s){
  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >que;
  fill_n(d[s],MAX_V,Inf);
  d[s][s] = 0;
  que.push(pair<int,int>(0,s));
  while(!que.empty()){
    pair<int,int> p=que.top();que.pop();
    int v = p.second;
    if(d[s][v]<p.first)continue;
    for(int j=0;j<E[v].size();j++){
      edge t = E[v][j];
      if(d[s][t.to]>d[s][v]+t.cost){
	d[s][t.to]=d[s][v]+t.cost;
	que.push(pair<int,int>(d[s][t.to],t.to));
      }
    }
  }
}
int main(){
  int n,m,r,t;cin>>n>>m>>r>>t;
  for(int i=0;i<m;i++){
    int a,b,c;cin>>a>>b>>c;
    edge e;e.to=b-1;e.cost=c;
    E[a-1].pb(e);
    e.to=a-1;
    E[b-1].pb(e);
  }
  for(int i=0;i<n;i++)
    dijkstra(i);
  int ans=0;
  vector<vector<double> >kame(n);
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i==j)continue;
      kame[i].pb((double)d[j][i]/t);
    }
    sort(ALL(kame[i]));
  }

  for(int i=0;i<n;i++){//mokuteki
    for(int j=0;j<n;j++){//usa
      if(i==j)continue;
      ans+=lower_bound(ALL(kame[i]),(double)d[j][i]/r-0.0000000001)-kame[i].begin();
      // cout<<i<<" "<<j<<" "<<ans<<endl;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result