Submission #2336825
Source Code Expand
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <queue> #include <set> #include <map> #include <cmath> using namespace std; using i64 = long long; using P = pair<i64,i64>; #define rep(i,s,e) for(int (i) = (s);i <= (e);(i)++) i64 N,M; i64 R,T; struct edge{ int to; i64 cost; }; vector<vector<edge>> edges(3000); i64 solve(int s){ vector<i64> dist(N,1e18); { priority_queue<P,vector<P>,greater<P>> que; dist[s] = 0; que.emplace(dist[s],s); while(!que.empty()){ int v = que.top().second; i64 d = que.top().first; que.pop(); if(dist[v] < d) continue; for(auto & e : edges[v]){ if(dist[e.to] > d + e.cost){ dist[e.to] = d + e.cost; que.emplace(dist[e.to] , e.to); } } } } sort(begin(dist),end(dist)); i64 res = 0; rep(i,1,N - 1){ i64 ite = upper_bound(begin(dist),end(dist),dist[i] * R / T) - begin(dist); res += N - ite; if(ite <= i) res--; } return res; } int main(){ cin >> N >> M >> R >> T; rep(i,0,M - 1){ int a,b; i64 c; cin >> a >> b >> c; a--; b--; edges[a].push_back({b,c}); edges[b].push_back({a,c}); } i64 res = 0; rep(i,0,N - 1){ res += solve(i); } cout << res << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | niuez |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1387 Byte |
Status | AC |
Exec Time | 1125 ms |
Memory | 512 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 | 1 ms | 256 KB |
subtask0_sample-02.txt | AC | 1 ms | 256 KB |
subtask1_01.txt | AC | 1 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | AC | 1 ms | 256 KB |
subtask1_04.txt | AC | 1 ms | 256 KB |
subtask1_05.txt | AC | 6 ms | 384 KB |
subtask1_06.txt | AC | 8 ms | 384 KB |
subtask1_07.txt | AC | 29 ms | 512 KB |
subtask1_08.txt | AC | 37 ms | 384 KB |
subtask1_09.txt | AC | 330 ms | 512 KB |
subtask1_10.txt | AC | 318 ms | 384 KB |
subtask1_11.txt | AC | 136 ms | 512 KB |
subtask1_12.txt | AC | 1032 ms | 512 KB |
subtask1_13.txt | AC | 1021 ms | 512 KB |
subtask1_14.txt | AC | 1120 ms | 512 KB |
subtask1_15.txt | AC | 755 ms | 512 KB |
subtask1_16.txt | AC | 1125 ms | 512 KB |