Submission #2888480
Source Code Expand
#include <algorithm> #include <cmath> #include <iostream> #include <queue> #include <tuple> #include <utility> #include <vector> #define llong long long using namespace std; const int IINF = 2147483647; const llong LLINF = 9223372036854775807; vector<llong> DJK(int n, int s, vector<vector<pair<int, llong>>> &E) { vector<pair<llong, bool>> V(n); for (int i = 0; i < n; i++) V[i] = make_pair(-1, false); V[s].first = 0; priority_queue<pair<llong, int>> Q; Q.push(make_pair(-V[s].first, s)); while (!Q.empty()) { int m = Q.top().second; Q.pop(); if (V[m].second) continue; V[m].second = true; for (pair<int, llong> p : E[m]) { int pd = p.first; llong plen = p.second; if (V[pd].first < 0) V[pd].first = LLINF; if (V[m].first + plen < V[pd].first) { V[pd].first = V[m].first + plen; Q.push(make_pair(-V[pd].first, pd)); } } } vector<llong> ret(n); for (int i = 0; i < n; i++) ret[i] = V[i].first; return ret; } int main(){ int n, m, s, t; cin >> n >> m >> s >> t; vector<vector<pair<int, llong>>>uva(n), uvb(n); for(int i=0; i<m; i++){ int u, v, a, b; cin >> u >> v >> a >> b; uva[u-1].push_back(make_pair(v-1, a)); uva[v-1].push_back(make_pair(u-1, a)); uvb[u-1].push_back(make_pair(v-1, b)); uvb[v-1].push_back(make_pair(u-1, b)); } vector<llong>ca=DJK(n, s-1, uva), cb=DJK(n, t-1, uvb), c(n); for(int i=0; i<n; i++)c[i]=ca[i]+cb[i]; llong mc=c[n-1]; vector<llong>ret(n); for(int i=n-1; i>=0; i--){ mc = min(mc, c[i]); ret[i]=1000000000000000-mc; } for(int i=0; i<n; i++)cout << ret[i] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Saving Snuuk |
User | settyan117 |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1888 Byte |
Status | AC |
Exec Time | 378 ms |
Memory | 20540 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 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 | 325 ms | 19940 KB |
11_0.txt | AC | 298 ms | 16520 KB |
11_1.txt | AC | 162 ms | 11576 KB |
11_2.txt | AC | 203 ms | 12284 KB |
11_3.txt | AC | 366 ms | 20020 KB |
11_4.txt | AC | 322 ms | 18128 KB |
1n1m1.txt | AC | 252 ms | 14520 KB |
1oo_0.txt | AC | 263 ms | 15968 KB |
1oo_1.txt | AC | 272 ms | 16524 KB |
1oo_2.txt | AC | 108 ms | 8576 KB |
1oo_3.txt | AC | 287 ms | 17576 KB |
1oo_4.txt | AC | 270 ms | 16520 KB |
dangou_0.txt | AC | 117 ms | 9216 KB |
dangou_1.txt | AC | 204 ms | 12472 KB |
dangou_2.txt | AC | 303 ms | 16932 KB |
dangou_3.txt | AC | 87 ms | 6312 KB |
dangou_4.txt | AC | 369 ms | 20540 KB |
edge.txt | AC | 352 ms | 20452 KB |
high_0.txt | AC | 117 ms | 7560 KB |
high_1.txt | AC | 147 ms | 9988 KB |
high_2.txt | AC | 348 ms | 19356 KB |
high_3.txt | AC | 19 ms | 1664 KB |
high_4.txt | AC | 267 ms | 14728 KB |
low_0.txt | AC | 94 ms | 11008 KB |
low_1.txt | AC | 100 ms | 9264 KB |
low_2.txt | AC | 277 ms | 17708 KB |
low_3.txt | AC | 244 ms | 16020 KB |
low_4.txt | AC | 166 ms | 12380 KB |
oo1_0.txt | AC | 294 ms | 18352 KB |
oo1_1.txt | AC | 239 ms | 15100 KB |
oo1_2.txt | AC | 197 ms | 13132 KB |
oo1_3.txt | AC | 150 ms | 11492 KB |
oo1_4.txt | AC | 193 ms | 12916 KB |
path_0.txt | AC | 303 ms | 17480 KB |
path_1.txt | AC | 302 ms | 16844 KB |
path_2.txt | AC | 144 ms | 8436 KB |
path_3.txt | AC | 183 ms | 10440 KB |
path_4.txt | AC | 97 ms | 6076 KB |
path_5.txt | AC | 268 ms | 15344 KB |
rnd_0.txt | AC | 299 ms | 16340 KB |
rnd_1.txt | AC | 378 ms | 19568 KB |
rnd_2.txt | AC | 37 ms | 2432 KB |
rnd_3.txt | AC | 341 ms | 18656 KB |
rnd_4.txt | AC | 210 ms | 12956 KB |
sampleRnd.txt | AC | 1 ms | 256 KB |
sampleT.txt | AC | 1 ms | 256 KB |
slast_0.txt | AC | 295 ms | 16008 KB |
slast_1.txt | AC | 136 ms | 8192 KB |
slast_2.txt | AC | 354 ms | 19340 KB |
slast_3.txt | AC | 227 ms | 13472 KB |
slast_4.txt | AC | 306 ms | 17020 KB |
tlast_0.txt | AC | 157 ms | 10564 KB |
tlast_1.txt | AC | 277 ms | 15356 KB |
tlast_2.txt | AC | 332 ms | 18764 KB |
tlast_3.txt | AC | 363 ms | 20012 KB |
tlast_4.txt | AC | 367 ms | 20012 KB |