Submission #2935141

---

Source Code Expand

#include <iostream>
#include <algorithm>
#define INF 1000000
#define MAX_V 3000
using namespace std;
int cost[MAX_V][MAX_V];
int d[MAX_V],e[3000][3000];
bool used[MAX_V];
int V;
void dijkstra(int s){
	fill (d,d+V,INF);
	fill (used,used+V,false);
	d[s] = 0;
	
	while(true){
		int v = -1;
		for(int u=0;u<V;u++){
			if(used[u]!=true && (v==-1 || d[u]<d[v])){
				v = u;
			}
		}
		//cout << v << endl;
		if(v==-1){
			break;
		}
		used[v] = true;
		for(int u=0;u<V;u++){
			d[u] = min(d[u],d[v]+cost[v][u]);
			//cout << d[u] << " " << u << endl;
		}
	}
}

int main(){
	int i,j,k,n,m,r,t,ans=0;
	cin >> n >> m >> r >> t;
	V = n;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			cost[i][j] = INF ;
		}
	}
	
	for(i=0;i<m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		a--; b--;
		cost[a][b] = c;
		cost[b][a] = c;
	}
	for(i=0;i<n;i++){
		dijkstra(i);
		for(j=0;j<n;j++){
			e[i][j] = d[j];
		}
	}
	
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			for(k=0;k<n;k++){
				if(i==j || j==k || i==k){
					continue;
				}else{
					if((double)e[i][j]/(double)r>(double)e[i][k]/(double)t){
						ans++;
					}
				}
			}
		}
	}
	cout << ans << endl;
}
						
		

Submission Info

Judge Result