Submission #1481447
Source Code Expand
#include<bits/stdc++.h> using namespace std; const int INF = 1 << 29; typedef pair< int, int > Pi; struct edge { int to, cost; }; typedef vector< vector< edge > > Graph; int Dijkstra(Graph &graph, int s, int g, vector< int > &min_cost) { min_cost.assign(graph.size(), INF); priority_queue< Pi, vector< Pi >, greater<> > que; que.push(make_pair(0, s)); min_cost[s] = 0; while(!que.empty()) { int now = que.top().second; int cost = que.top().first; que.pop(); if(now == g) return (cost); if(cost > min_cost[now]) continue; for(int i = 0; i < graph[now].size(); i++) { edge &e = graph[now][i]; if(cost + e.cost < min_cost[e.to]) { min_cost[e.to] = cost + e.cost; que.emplace(min_cost[e.to], e.to); } } } return (-1); } int main() { int N, M, R, T; cin >> N >> M >> R >> T; Graph g(N); for(int i = 0; i < M; i++) { int A, B, C; cin >> A >> B >> C; --A, --B; g[A].push_back((edge) {B, C}); g[B].push_back((edge) {A, C}); } int ret = 0; for(int C = 0; C < N; C++) { vector< int > st; Dijkstra(g, C, -1, st); sort(begin(st), end(st)); int tail = 1; for(int i = 1; i < st.size(); i++) { while(tail < st.size() && 1LL * st[tail] * T <= 1LL * st[i] * R) ++tail; ret += st.size() - tail; if(tail <= i) --ret; } } cout << ret << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | ei13333 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1456 Byte |
Status | WA |
Exec Time | 994 ms |
Memory | 384 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 | 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 | 256 KB |
subtask1_07.txt | AC | 29 ms | 384 KB |
subtask1_08.txt | AC | 36 ms | 256 KB |
subtask1_09.txt | AC | 300 ms | 384 KB |
subtask1_10.txt | AC | 279 ms | 384 KB |
subtask1_11.txt | AC | 126 ms | 384 KB |
subtask1_12.txt | WA | 894 ms | 384 KB |
subtask1_13.txt | WA | 888 ms | 384 KB |
subtask1_14.txt | WA | 987 ms | 384 KB |
subtask1_15.txt | AC | 675 ms | 384 KB |
subtask1_16.txt | WA | 994 ms | 384 KB |