Submission #2935677


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));
	}
	long long 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));
				}
			}
		}
		sort(CR.begin()+1,CR.begin()+N+1);
		for(int i=2;i<=N;i++){
			//if(R>=T){
				decltype(CR)::iterator it = upper_bound(CR.begin(),CR.end(),CR[i]*R/T);
				ans += (N-(it-CR.begin()-1));
			}
			/*else{
				decltype(CR)::iterator it = lower_bound(CR.begin(),CR.end(),CR[i]*T/R);
				//cout << it-CR.begin()-1 << endl;
				ans += (it-CR.begin()-i);
			}*/
		}
	}
	if(R<T) ans -= N*(N-1);
	cout << ans << endl;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User idsigma
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1283 Byte
Status CE

Compile Error

./Main.cpp:53:2: error: expected unqualified-id before ‘if’
  if(R<T) ans -= N*(N-1);
  ^
./Main.cpp:54:2: error: ‘cout’ does not name a type
  cout << ans << endl;
  ^
./Main.cpp:55:1: error: expected declaration before ‘}’ token
 }
 ^