Submission #184204
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int N = 2525; int n,m,r,t; struct edge{int to,cost;}; vector<edge> G[N]; typedef pair<int,int> P; int d[N], e[N]; int dijkstra(int s){ fill(d,d+n,INT_MAX/2); priority_queue<P,vector<P>,greater<P>> pq; pq.push({0,s}); d[s] = 0; while(!pq.empty()){ int v = pq.top().second; int l = pq.top().first; pq.pop(); if(d[v] < l) continue; for(edge &e : G[v]){ int w = e.to; int c = e.cost; if(d[w] > d[v] + c){ d[w] = d[v] + c; pq.push({d[w],w}); } } } sort(d,d+n); for(int i = 0; i < n; i++){ e[i] = d[i] * t; d[i] *= r; assert(e[i] >= 0 && d[i] >= 0); } int res = 0; if(n <= 600){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i == j || i == 0 || j == 0) continue; res += d[i]*t > d[j]*r; } } } else { for(int i = 1; i < n; i++){ res += lower_bound(d, d+n, e[i]) - d - 1; if(r < t) res--; } } return res; } int main(){ cin >> n >> m >> r >> t; for(int i = 0; i < m; i++){ int a,b,c; cin >> a >> b >> c; G[a-1].push_back({b-1,c}); G[b-1].push_back({a-1,c}); } long long ans = 0; for(int a = 0; a < n; a++){ ans += dijkstra(a); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | eha |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 1596 Byte |
Status | AC |
Exec Time | 1549 ms |
Memory | 1056 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 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 | 21 ms | 792 KB |
subtask0_sample-02.txt | AC | 21 ms | 804 KB |
subtask1_01.txt | AC | 21 ms | 924 KB |
subtask1_02.txt | AC | 21 ms | 924 KB |
subtask1_03.txt | AC | 22 ms | 932 KB |
subtask1_04.txt | AC | 21 ms | 928 KB |
subtask1_05.txt | AC | 52 ms | 800 KB |
subtask1_06.txt | AC | 55 ms | 928 KB |
subtask1_07.txt | AC | 138 ms | 928 KB |
subtask1_08.txt | AC | 258 ms | 872 KB |
subtask1_09.txt | AC | 457 ms | 1056 KB |
subtask1_10.txt | AC | 442 ms | 860 KB |
subtask1_11.txt | AC | 202 ms | 928 KB |
subtask1_12.txt | AC | 1420 ms | 928 KB |
subtask1_13.txt | AC | 1415 ms | 936 KB |
subtask1_14.txt | AC | 1549 ms | 1056 KB |
subtask1_15.txt | AC | 1021 ms | 932 KB |
subtask1_16.txt | AC | 1542 ms | 1048 KB |