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 } ^