Submission #2935296

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<double,int> P;
int N,M;
const double inf = 1e9;
double a,b,c,R,T;
vector<vector<P>> v(2510),u(2510);
int main(){
	cin >> N >> M >> R >> T;
	for(int i=0;i<M;i++){
		cin >> a >> b >> c;
		v[a].push_back(P(c,b));
		v[b].push_back(P(c,a));
//		u[a].push_back(P(c/T,b));
//		u[a].push_back(P(c/T,a));
	}
	int ans = 0;
	vector<double> CR(N+1);
	for(int r=1;r<=N;r++){
		priority_queue<P> Q;
		Q.push(P(0,r));
		for(int i=1;i<=N;i++){
			CR[i] = inf;
		}
		CR[r] = 0;
		while(!Q.empty()){
			P t = Q.top();
			int  s = t.second;
			Q.pop();
			if(CR[s] < t.first) continue;
			for(int i=0;i<v[s].size();i++){
				P e = v[s][i];
				if(CR[e.second] > CR[s] + e.first){
					CR[e.second] = CR[s] + e.first;
					Q.push(make_pair(-CR[e.second],e.second));
				}
			}
		}
/*		Q.push(P(0,r));
		for(int i=1;i<=N;i++){
			CT[i] = inf;
		}
		CT[r] = 0;
		while(!Q.empty()){
			P t = Q.top();
			int s = t.second;
			Q.pop();
			if(CT[s] < t.first) continue;
			for(int i=0;i<u[s].size();i++){
				P e = u[s][i];
				if(CT[e.second] > CT[s] + e.first){
					CT[e.second] = CT[s] + e.first;
					Q.push(make_pair(-CT[e.second],e.second));
				}
			}
		}*/
		sort(CR.begin()+1,CR.begin()+N+1);
		//sort(CT+1,CT+N+1);
		for(int i=2;i<=N;i++){
			if(R>=T){
				decltype(CR)::iterator it = upper_bound(CR.begin()+i,CR.end(),CR[i]*R/T);
		//		if(r==1) cout << it-CR.begin()-1 << endl;
				ans += (N-(it-CR.begin()-1));
			}
			else{
				decltype(CR)::iterator it = upper_bound(CR.begin()+i,CR.end(),CR[i]*T/R);
		//		if(r==1) cout << it-CR.begin()-1 << endl;
				ans += (N-(it-CR.begin()-1));
			}
		}
	}
	cout << ans << endl;
}

Submission Info

Judge Result