Submission #1533766
Source Code Expand
#include "bits/stdc++.h" using namespace std; #define OUT(x) cerr << #x << " = " << x << endl; #define all(x) x.begin(), x.end() #define mp make_pair #define pii pair<int, int> #define pll pair<long long, long long> #define ll long long #define int long long struct edge { int to, cost; edge(int to, int cost) : to(to), cost(cost) { }; bool operator > (const edge &r) const { return cost > r.cost; } bool operator < (const edge &r) const { return cost < r.cost; } }; static const int INF = 0x3f3f3f3f; vector<edge> g[101010]; int n; void dijkstra(int start, vector<int> &dis) { priority_queue<edge, vector<edge>, greater<edge>> q; dis[start] = 0; q.push((edge){ start, 0 }); while (!q.empty()) { edge e1 = q.top(); q.pop(); for (auto e2 : g[e1.to]) { if (dis[e2.to] > dis[e1.to] + e2.cost) { dis[e2.to] = dis[e1.to] + e2.cost; q.push((edge){ e2.to, dis[e2.to] }); } } } } signed main() { int n, m; double r, t; cin >> n >> m >> r >> t; vector<int> d(n); for (int i = 0; i < m; i ++) { int a, b, c; cin >> a >> b >> c; a --, b --; g[a].push_back({b, c}); g[b].push_back({a, c}); } int ans = 0; for (int goal = 0; goal < n; goal ++) { vector<int> dis(n, INF); dijkstra(goal, dis); sort(all(dis)); for (int a = 1; a < n; a ++) { int dis_t = dis[a]; int dis_r = dis_t * r / t + 1; int res = lower_bound(all(dis), dis_r) - dis.begin(); int cnt = n - res; if (res <= a) cnt --; ans += cnt; } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | KokiYmgch |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2140 Byte |
Status | AC |
Exec Time | 844 ms |
Memory | 2816 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 | 2 ms | 2560 KB |
subtask0_sample-02.txt | AC | 2 ms | 2560 KB |
subtask1_01.txt | AC | 3 ms | 2560 KB |
subtask1_02.txt | AC | 3 ms | 2560 KB |
subtask1_03.txt | AC | 3 ms | 2560 KB |
subtask1_04.txt | AC | 2 ms | 2560 KB |
subtask1_05.txt | AC | 6 ms | 2688 KB |
subtask1_06.txt | AC | 8 ms | 2688 KB |
subtask1_07.txt | AC | 25 ms | 2816 KB |
subtask1_08.txt | AC | 29 ms | 2688 KB |
subtask1_09.txt | AC | 245 ms | 2816 KB |
subtask1_10.txt | AC | 242 ms | 2688 KB |
subtask1_11.txt | AC | 101 ms | 2816 KB |
subtask1_12.txt | AC | 776 ms | 2816 KB |
subtask1_13.txt | AC | 774 ms | 2816 KB |
subtask1_14.txt | AC | 836 ms | 2816 KB |
subtask1_15.txt | AC | 572 ms | 2816 KB |
subtask1_16.txt | AC | 844 ms | 2816 KB |