Submission #2935253
Source Code Expand
#include <bits/stdc++.h> using namespace std; using lint = long long; template<class T = int> using V = vector<T>; template<class T = int> using VV = V< V<T> >; using P = pair<int, int>; int main() { cin.tie(NULL); ios::sync_with_stdio(false); int n, m, r, t; cin >> n >> m >> r >> t; struct edge { int to, w; }; VV<edge> 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}); } lint res = 0; for (int i = 0; i < n; i++) { priority_queue<P, V<P>, greater<P> > q; V<> d(n, 1e9); d[i] = 0; q.emplace(0, i); while (not q.empty()) { P p = q.top(); q.pop(); int v = p.second; if (p.first > d[v]) continue; for (auto&& e : g[v]) { if (d[e.to] < d[v] + e.w) continue; d[e.to] = d[v] + e.w; q.emplace(d[e.to], e.to); } } sort(d.begin(), d.end()); for (int j = 0; j < n; j++) { if (i == j) continue; res += d.end() - upper_bound(d.begin(), d.end(), d[i] * r / t); } } if (t > r) res -= n; cout << res << '\n'; }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | risujiroh |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1139 Byte |
Status | WA |
Exec Time | 1124 ms |
Memory | 512 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 | WA | 1 ms | 256 KB |
subtask0_sample-02.txt | WA | 1 ms | 256 KB |
subtask1_01.txt | WA | 1 ms | 256 KB |
subtask1_02.txt | WA | 1 ms | 256 KB |
subtask1_03.txt | WA | 1 ms | 256 KB |
subtask1_04.txt | WA | 1 ms | 256 KB |
subtask1_05.txt | WA | 6 ms | 256 KB |
subtask1_06.txt | WA | 9 ms | 256 KB |
subtask1_07.txt | WA | 41 ms | 384 KB |
subtask1_08.txt | WA | 42 ms | 384 KB |
subtask1_09.txt | WA | 357 ms | 384 KB |
subtask1_10.txt | WA | 321 ms | 384 KB |
subtask1_11.txt | WA | 153 ms | 384 KB |
subtask1_12.txt | WA | 955 ms | 384 KB |
subtask1_13.txt | WA | 951 ms | 384 KB |
subtask1_14.txt | WA | 1116 ms | 512 KB |
subtask1_15.txt | WA | 788 ms | 384 KB |
subtask1_16.txt | WA | 1124 ms | 512 KB |