# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
116948 | 2019-06-14T08:16:17 Z | roseanne_pcy | Commuter Pass (JOI18_commuter_pass) | C++14 | 524 ms | 22056 KB |
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; const int maxn = 1e5+5; vector< ii > adj[maxn]; int n, m; int s, t, U, V; ll udist[maxn]; ll vdist[maxn]; ll tdist[maxn]; ll sdist[maxn]; ll udp[maxn]; ll vdp[maxn]; void dijk(int S, ll *dist) { for(int i = 1; i<= n; i++) dist[i] = 4e18; dist[S] = 0; priority_queue< pair<ll, int> > pq; pq.push({0, S}); while(!pq.empty()) { auto x = pq.top(); pq.pop(); int u = x.Y, d = -x.X; if(d> dist[u]) continue; for(auto kk : adj[u]) { int v = kk.X, w = kk.Y; if(dist[v]> dist[u]+w) { dist[v] = dist[u]+w; pq.push({-dist[v], v}); } } } } vector<int> buck[maxn]; bool cmp(int a, int b) { return tdist[a]< tdist[b]; } int main() { scanf("%d %d", &n, &m); scanf("%d %d %d %d", &s, &t, &U, &V); for(int i = 1; i<= m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w)); } dijk(U, udist); dijk(V, vdist); dijk(t, tdist); dijk(s, sdist); vector<int> vec; for(int i = 1; i<= n; i++) if(i != t) vec.pb(i); sort(vec.begin(), vec.end(), cmp); udp[t] = udist[t]; vdp[t] = vdist[t]; ll best = udist[V]; for(int u : vec) { udp[u] = udist[u]; vdp[u] = vdist[u]; for(auto kk : adj[u]) { int v = kk.X, w = kk.Y; if(tdist[u] == tdist[v]+w) { udp[u] = min(udp[u], udp[v]); vdp[u] = min(vdp[u], vdp[v]); } } if(sdist[u] + tdist[u] != sdist[t]) continue; best = min(best, udp[u]+vdist[u]); best = min(best, vdp[u]+udist[u]); } printf("%lld\n", best); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 443 ms | 21412 KB | Output is correct |
2 | Correct | 475 ms | 20460 KB | Output is correct |
3 | Correct | 492 ms | 21412 KB | Output is correct |
4 | Correct | 471 ms | 22056 KB | Output is correct |
5 | Correct | 479 ms | 20392 KB | Output is correct |
6 | Correct | 468 ms | 21604 KB | Output is correct |
7 | Correct | 408 ms | 20436 KB | Output is correct |
8 | Correct | 477 ms | 20496 KB | Output is correct |
9 | Correct | 471 ms | 21272 KB | Output is correct |
10 | Correct | 358 ms | 21316 KB | Output is correct |
11 | Correct | 193 ms | 15496 KB | Output is correct |
12 | Correct | 513 ms | 21380 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 506 ms | 20648 KB | Output is correct |
2 | Correct | 489 ms | 20588 KB | Output is correct |
3 | Correct | 513 ms | 20512 KB | Output is correct |
4 | Correct | 508 ms | 20440 KB | Output is correct |
5 | Correct | 524 ms | 20632 KB | Output is correct |
6 | Correct | 423 ms | 20788 KB | Output is correct |
7 | Correct | 473 ms | 20520 KB | Output is correct |
8 | Correct | 447 ms | 20612 KB | Output is correct |
9 | Correct | 429 ms | 20416 KB | Output is correct |
10 | Correct | 448 ms | 20540 KB | Output is correct |
11 | Correct | 175 ms | 15476 KB | Output is correct |
12 | Correct | 402 ms | 20596 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 6144 KB | Output is correct |
2 | Correct | 7 ms | 5120 KB | Output is correct |
3 | Correct | 7 ms | 5120 KB | Output is correct |
4 | Correct | 25 ms | 7168 KB | Output is correct |
5 | Correct | 14 ms | 6140 KB | Output is correct |
6 | Correct | 7 ms | 5120 KB | Output is correct |
7 | Correct | 7 ms | 5248 KB | Output is correct |
8 | Correct | 8 ms | 5248 KB | Output is correct |
9 | Correct | 7 ms | 5120 KB | Output is correct |
10 | Correct | 15 ms | 6144 KB | Output is correct |
11 | Correct | 6 ms | 5120 KB | Output is correct |
12 | Correct | 6 ms | 5120 KB | Output is correct |
13 | Correct | 6 ms | 5120 KB | Output is correct |
14 | Correct | 8 ms | 5120 KB | Output is correct |
15 | Correct | 6 ms | 5120 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 443 ms | 21412 KB | Output is correct |
2 | Correct | 475 ms | 20460 KB | Output is correct |
3 | Correct | 492 ms | 21412 KB | Output is correct |
4 | Correct | 471 ms | 22056 KB | Output is correct |
5 | Correct | 479 ms | 20392 KB | Output is correct |
6 | Correct | 468 ms | 21604 KB | Output is correct |
7 | Correct | 408 ms | 20436 KB | Output is correct |
8 | Correct | 477 ms | 20496 KB | Output is correct |
9 | Correct | 471 ms | 21272 KB | Output is correct |
10 | Correct | 358 ms | 21316 KB | Output is correct |
11 | Correct | 193 ms | 15496 KB | Output is correct |
12 | Correct | 513 ms | 21380 KB | Output is correct |
13 | Correct | 506 ms | 20648 KB | Output is correct |
14 | Correct | 489 ms | 20588 KB | Output is correct |
15 | Correct | 513 ms | 20512 KB | Output is correct |
16 | Correct | 508 ms | 20440 KB | Output is correct |
17 | Correct | 524 ms | 20632 KB | Output is correct |
18 | Correct | 423 ms | 20788 KB | Output is correct |
19 | Correct | 473 ms | 20520 KB | Output is correct |
20 | Correct | 447 ms | 20612 KB | Output is correct |
21 | Correct | 429 ms | 20416 KB | Output is correct |
22 | Correct | 448 ms | 20540 KB | Output is correct |
23 | Correct | 175 ms | 15476 KB | Output is correct |
24 | Correct | 402 ms | 20596 KB | Output is correct |
25 | Correct | 14 ms | 6144 KB | Output is correct |
26 | Correct | 7 ms | 5120 KB | Output is correct |
27 | Correct | 7 ms | 5120 KB | Output is correct |
28 | Correct | 25 ms | 7168 KB | Output is correct |
29 | Correct | 14 ms | 6140 KB | Output is correct |
30 | Correct | 7 ms | 5120 KB | Output is correct |
31 | Correct | 7 ms | 5248 KB | Output is correct |
32 | Correct | 8 ms | 5248 KB | Output is correct |
33 | Correct | 7 ms | 5120 KB | Output is correct |
34 | Correct | 15 ms | 6144 KB | Output is correct |
35 | Correct | 6 ms | 5120 KB | Output is correct |
36 | Correct | 6 ms | 5120 KB | Output is correct |
37 | Correct | 6 ms | 5120 KB | Output is correct |
38 | Correct | 8 ms | 5120 KB | Output is correct |
39 | Correct | 6 ms | 5120 KB | Output is correct |
40 | Correct | 397 ms | 21824 KB | Output is correct |
41 | Correct | 447 ms | 21272 KB | Output is correct |
42 | Correct | 402 ms | 21456 KB | Output is correct |
43 | Correct | 165 ms | 15476 KB | Output is correct |
44 | Correct | 156 ms | 15448 KB | Output is correct |
45 | Correct | 414 ms | 20448 KB | Output is correct |
46 | Correct | 414 ms | 20156 KB | Output is correct |
47 | Correct | 435 ms | 21680 KB | Output is correct |
48 | Correct | 256 ms | 14984 KB | Output is correct |
49 | Correct | 376 ms | 21452 KB | Output is correct |
50 | Correct | 367 ms | 20488 KB | Output is correct |
51 | Correct | 368 ms | 20464 KB | Output is correct |