Submission #2818462
Source Code Expand
#include <bits/stdc++.h> using namespace std; struct edge { long long to, cost;}; typedef pair<long long, long long> Pair; vector<long long> dijkstra(long long s, long long n, const vector<edge> G[]){ vector<long long> dist = {}; long long INF = 1LL<<60; dist.resize(n); for(int i=0; i<n; i++){ dist[i] = INF; } priority_queue<Pair, vector<Pair>, greater<Pair>> que; dist[s] = 0; que.push(Pair(0, s)); while(!que.empty()){ Pair p = que.top(); que.pop(); long long v = p.second; if(dist[v] < p.first)continue; for(int i=0;i<G[v].size(); i++){ edge e = G[v][i]; if(dist[e.to] > dist[v] + e.cost){ dist[e.to] = dist[v] + e.cost; que.push(Pair(dist[e.to], e.to)); } } } return dist; } int main(){ long long i, j, k; long long N, M, R, T; vector<edge> edges[2500]; cin >> N >> M >> R >> T; for(i=0; i<M; i++){ long long a, b, c; cin >> a >> b >> c; edges[a-1].push_back({b-1, c}); edges[b-1].push_back({a-1, c}); } long long ans = 0; for(i=0; i<N; i++){ vector<long long> dist = dijkstra(i, N, edges); sort(dist.begin(), dist.end()); long long t = 0; for(long long r=1; r<N; r++){ while(t<N-1 && R*dist[t+1] < T*dist[r]) t++; ans += (t>=r) ? t-1 : t; } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | betrue12 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1548 Byte |
Status | AC |
Exec Time | 1005 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 | 256 KB |
subtask1_06.txt | AC | 8 ms | 384 KB |
subtask1_07.txt | AC | 28 ms | 512 KB |
subtask1_08.txt | AC | 35 ms | 384 KB |
subtask1_09.txt | AC | 298 ms | 512 KB |
subtask1_10.txt | AC | 275 ms | 384 KB |
subtask1_11.txt | AC | 124 ms | 384 KB |
subtask1_12.txt | AC | 889 ms | 512 KB |
subtask1_13.txt | AC | 885 ms | 512 KB |
subtask1_14.txt | AC | 986 ms | 512 KB |
subtask1_15.txt | AC | 680 ms | 512 KB |
subtask1_16.txt | AC | 1005 ms | 512 KB |