Submission #2935411
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)); } 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)); } } } 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 = upper_bound(CR.begin(),CR.end(),CR[i]*T/R); //cout << it-CR.begin()-1 << endl; ans += (it-CR.begin()-i-1); } // if(R<T) ans = N*N*N-ans; } } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | idsigma |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1276 Byte |
Status | WA |
Exec Time | 1202 ms |
Memory | 640 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample-01.txt, subtask0_sample-02.txt |
All | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample-01.txt | AC | 1 ms | 384 KB |
subtask0_sample-02.txt | AC | 1 ms | 384 KB |
subtask1_01.txt | AC | 1 ms | 384 KB |
subtask1_02.txt | AC | 1 ms | 384 KB |
subtask1_03.txt | AC | 1 ms | 384 KB |
subtask1_04.txt | AC | 1 ms | 384 KB |
subtask1_05.txt | AC | 7 ms | 384 KB |
subtask1_06.txt | WA | 9 ms | 384 KB |
subtask1_07.txt | AC | 38 ms | 512 KB |
subtask1_08.txt | WA | 43 ms | 512 KB |
subtask1_09.txt | AC | 356 ms | 640 KB |
subtask1_10.txt | AC | 333 ms | 512 KB |
subtask1_11.txt | AC | 149 ms | 512 KB |
subtask1_12.txt | WA | 1104 ms | 512 KB |
subtask1_13.txt | WA | 1092 ms | 512 KB |
subtask1_14.txt | WA | 1200 ms | 512 KB |
subtask1_15.txt | AC | 808 ms | 512 KB |
subtask1_16.txt | WA | 1202 ms | 640 KB |