Submission #3609370
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define rep(i, j, n) for(int i=j;i<n;++i) #define all(i) i.begin(),i.end() #define rall(i) i.rbegin(),i.rend() #define INF 1e9 const int mod = 1e9 + 7; typedef long long i64; typedef pair<int, int> pi; template <class T> using vt = vector<T>; template <class T> using vvt = vector<vector<T>>; i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));} i64 lcm(i64 n, i64 m) {return (n / gcd(n, m) * m);} int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; vvt<pair<int, int>> edge; vt<i64> dijkstra(int s, vt<i64> &cost) { vt<i64> dist(101000, 1e18); dist[s] = 0; priority_queue<pair<int, i64>, vt<pair<int, i64>>, greater<pair<int, i64>>> que; que.push({s, 0}); while(!que.empty()) { auto p = que.top(); que.pop(); int v = p.first; i64 d = p.second; if(dist[v] < d) continue; for(auto &nxt : edge[v]) { if(dist[nxt.first] < dist[v] + cost[nxt.second]) continue; dist[nxt.first] = dist[v] + cost[nxt.second]; que.push({nxt.first, dist[nxt.first]}); } } return dist; } int main() { cin.tie(0); ios::sync_with_stdio(false); int n, m, s, t; cin >> n >> m >> s >> t; s--; t--; vt<i64> a(m), b(m); edge.resize(n); rep(i, 0, m) { int u, v; cin >> u >> v >> a[i] >> b[i]; u--; v--; edge[u].push_back({v, i}); edge[v].push_back({u, i}); } auto dist1 = dijkstra(s, a); auto dist2 = dijkstra(t, b); vt<i64> ans; i64 res = 0; for(int i = n - 1; i >= 0; --i) { res = max(res, (i64)1e15 - dist1[i] - dist2[i]); ans.push_back(res); } for(int i = n - 1; i >= 0; --i) cout << ans[i] << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - Saving Snuuk |
User | playroller |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1745 Byte |
Status | TLE |
Exec Time | 2105 ms |
Memory | 529108 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sampleRnd.txt, sampleT.txt |
All | 00yorimichi.txt, 11_0.txt, 11_1.txt, 11_2.txt, 11_3.txt, 11_4.txt, 1n1m1.txt, 1oo_0.txt, 1oo_1.txt, 1oo_2.txt, 1oo_3.txt, 1oo_4.txt, dangou_0.txt, dangou_1.txt, dangou_2.txt, dangou_3.txt, dangou_4.txt, edge.txt, high_0.txt, high_1.txt, high_2.txt, high_3.txt, high_4.txt, low_0.txt, low_1.txt, low_2.txt, low_3.txt, low_4.txt, oo1_0.txt, oo1_1.txt, oo1_2.txt, oo1_3.txt, oo1_4.txt, path_0.txt, path_1.txt, path_2.txt, path_3.txt, path_4.txt, path_5.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sampleRnd.txt, sampleT.txt, slast_0.txt, slast_1.txt, slast_2.txt, slast_3.txt, slast_4.txt, tlast_0.txt, tlast_1.txt, tlast_2.txt, tlast_3.txt, tlast_4.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00yorimichi.txt | AC | 204 ms | 11380 KB |
11_0.txt | AC | 590 ms | 15360 KB |
11_1.txt | AC | 150 ms | 9552 KB |
11_2.txt | AC | 293 ms | 13768 KB |
11_3.txt | AC | 412 ms | 12672 KB |
11_4.txt | AC | 551 ms | 16296 KB |
1n1m1.txt | TLE | 2104 ms | 8500 KB |
1oo_0.txt | AC | 519 ms | 15024 KB |
1oo_1.txt | AC | 614 ms | 16164 KB |
1oo_2.txt | AC | 97 ms | 5752 KB |
1oo_3.txt | AC | 492 ms | 15304 KB |
1oo_4.txt | AC | 507 ms | 15444 KB |
dangou_0.txt | TLE | 2105 ms | 529108 KB |
dangou_1.txt | AC | 308 ms | 12912 KB |
dangou_2.txt | AC | 460 ms | 12048 KB |
dangou_3.txt | TLE | 2104 ms | 136412 KB |
dangou_4.txt | AC | 407 ms | 12712 KB |
edge.txt | AC | 229 ms | 11380 KB |
high_0.txt | AC | 90 ms | 6792 KB |
high_1.txt | AC | 104 ms | 8736 KB |
high_2.txt | AC | 485 ms | 12292 KB |
high_3.txt | AC | 7 ms | 2432 KB |
high_4.txt | AC | 229 ms | 9096 KB |
low_0.txt | AC | 77 ms | 6936 KB |
low_1.txt | AC | 99 ms | 7224 KB |
low_2.txt | AC | 492 ms | 11748 KB |
low_3.txt | AC | 417 ms | 11152 KB |
low_4.txt | AC | 289 ms | 11504 KB |
oo1_0.txt | AC | 632 ms | 15988 KB |
oo1_1.txt | AC | 472 ms | 15380 KB |
oo1_2.txt | AC | 393 ms | 14372 KB |
oo1_3.txt | AC | 195 ms | 9788 KB |
oo1_4.txt | AC | 338 ms | 15192 KB |
path_0.txt | AC | 192 ms | 9976 KB |
path_1.txt | AC | 190 ms | 9976 KB |
path_2.txt | AC | 92 ms | 5880 KB |
path_3.txt | AC | 116 ms | 6908 KB |
path_4.txt | AC | 64 ms | 4732 KB |
path_5.txt | AC | 166 ms | 8948 KB |
rnd_0.txt | AC | 424 ms | 14864 KB |
rnd_1.txt | AC | 544 ms | 14456 KB |
rnd_2.txt | AC | 15 ms | 2944 KB |
rnd_3.txt | AC | 487 ms | 12716 KB |
rnd_4.txt | AC | 277 ms | 15080 KB |
sampleRnd.txt | AC | 2 ms | 1792 KB |
sampleT.txt | AC | 2 ms | 1792 KB |
slast_0.txt | AC | 483 ms | 14956 KB |
slast_1.txt | AC | 52 ms | 5660 KB |
slast_2.txt | AC | 496 ms | 12900 KB |
slast_3.txt | AC | 335 ms | 14880 KB |
slast_4.txt | AC | 477 ms | 16372 KB |
tlast_0.txt | AC | 88 ms | 7552 KB |
tlast_1.txt | AC | 448 ms | 15428 KB |
tlast_2.txt | AC | 494 ms | 15296 KB |
tlast_3.txt | AC | 418 ms | 12684 KB |
tlast_4.txt | AC | 431 ms | 12704 KB |