# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
331813 | 2020-11-30T08:40:42 Z | arnold518 | Commuter Pass (JOI18_commuter_pass) | C++14 | 637 ms | 27024 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; const ll INF = 1e18; int N, M; vector<pii> adj[MAXN+10]; int S, T, U, V; ll DS[MAXN+10], DU[MAXN+10], DV[MAXN+10]; vector<int> adj2[MAXN+10]; struct Queue { int u; ll w; bool operator < (const Queue &p) const { return w>p.w; } }; void dijk(int S, ll *D) { priority_queue<Queue> PQ; for(int i=1; i<=N; i++) D[i]=INF; PQ.push({S, 0}); while(!PQ.empty()) { Queue now=PQ.top(); PQ.pop(); if(D[now.u]<=now.w) continue; D[now.u]=now.w; for(auto nxt : adj[now.u]) { PQ.push({nxt.first, now.w+nxt.second}); } } } bool vis[MAXN+10]; vector<int> ST; void dfs(int now) { vis[now]=true; for(int nxt : adj2[now]) { if(vis[nxt]) continue; dfs(nxt); } ST.push_back(now); } ll dp[MAXN+10][4]; 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].push_back({v, w}); adj[v].push_back({u, w}); } dijk(S, DS); dijk(U, DU); dijk(V, DV); for(int now=1; now<=N; now++) { for(auto nxt : adj[now]) { if(DS[nxt.first]==DS[now]+nxt.second) { adj2[now].push_back(nxt.first); } } } dfs(S); reverse(ST.begin(), ST.end()); for(int i=1; i<=N; i++) for(int j=0; j<4; j++) dp[i][j]=INF; dp[S][0]=0; for(auto now : ST) { dp[now][1]=min(dp[now][1], dp[now][0]+DU[now]); dp[now][2]=min(dp[now][2], dp[now][0]+DV[now]); dp[now][3]=min({dp[now][3], dp[now][2]+DU[now], dp[now][1]+DV[now], dp[now][0]+DU[now]+DV[now]}); for(auto nxt : adj2[now]) { for(int j=0; j<4; j++) { dp[nxt][j]=min(dp[nxt][j], dp[now][j]); } } } printf("%lld\n", min(DU[V], dp[T][3])); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 597 ms | 22396 KB | Output is correct |
2 | Correct | 532 ms | 21740 KB | Output is correct |
3 | Correct | 582 ms | 25176 KB | Output is correct |
4 | Correct | 567 ms | 21812 KB | Output is correct |
5 | Correct | 498 ms | 22144 KB | Output is correct |
6 | Correct | 637 ms | 22172 KB | Output is correct |
7 | Correct | 541 ms | 22184 KB | Output is correct |
8 | Correct | 544 ms | 22524 KB | Output is correct |
9 | Correct | 557 ms | 22044 KB | Output is correct |
10 | Correct | 430 ms | 22176 KB | Output is correct |
11 | Correct | 199 ms | 21860 KB | Output is correct |
12 | Correct | 558 ms | 22624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 533 ms | 23316 KB | Output is correct |
2 | Correct | 495 ms | 24860 KB | Output is correct |
3 | Correct | 516 ms | 23692 KB | Output is correct |
4 | Correct | 495 ms | 23992 KB | Output is correct |
5 | Correct | 503 ms | 23620 KB | Output is correct |
6 | Correct | 518 ms | 25272 KB | Output is correct |
7 | Correct | 550 ms | 27024 KB | Output is correct |
8 | Correct | 482 ms | 23744 KB | Output is correct |
9 | Correct | 500 ms | 23788 KB | Output is correct |
10 | Correct | 507 ms | 23680 KB | Output is correct |
11 | Correct | 198 ms | 22116 KB | Output is correct |
12 | Correct | 496 ms | 25316 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 6948 KB | Output is correct |
2 | Correct | 4 ms | 5100 KB | Output is correct |
3 | Correct | 5 ms | 5100 KB | Output is correct |
4 | Correct | 71 ms | 9096 KB | Output is correct |
5 | Correct | 29 ms | 7724 KB | Output is correct |
6 | Correct | 5 ms | 5248 KB | Output is correct |
7 | Correct | 6 ms | 5356 KB | Output is correct |
8 | Correct | 7 ms | 5356 KB | Output is correct |
9 | Correct | 5 ms | 5228 KB | Output is correct |
10 | Correct | 30 ms | 7688 KB | Output is correct |
11 | Correct | 4 ms | 5100 KB | Output is correct |
12 | Correct | 4 ms | 5100 KB | Output is correct |
13 | Correct | 5 ms | 5100 KB | Output is correct |
14 | Correct | 5 ms | 5100 KB | Output is correct |
15 | Correct | 5 ms | 5100 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 597 ms | 22396 KB | Output is correct |
2 | Correct | 532 ms | 21740 KB | Output is correct |
3 | Correct | 582 ms | 25176 KB | Output is correct |
4 | Correct | 567 ms | 21812 KB | Output is correct |
5 | Correct | 498 ms | 22144 KB | Output is correct |
6 | Correct | 637 ms | 22172 KB | Output is correct |
7 | Correct | 541 ms | 22184 KB | Output is correct |
8 | Correct | 544 ms | 22524 KB | Output is correct |
9 | Correct | 557 ms | 22044 KB | Output is correct |
10 | Correct | 430 ms | 22176 KB | Output is correct |
11 | Correct | 199 ms | 21860 KB | Output is correct |
12 | Correct | 558 ms | 22624 KB | Output is correct |
13 | Correct | 533 ms | 23316 KB | Output is correct |
14 | Correct | 495 ms | 24860 KB | Output is correct |
15 | Correct | 516 ms | 23692 KB | Output is correct |
16 | Correct | 495 ms | 23992 KB | Output is correct |
17 | Correct | 503 ms | 23620 KB | Output is correct |
18 | Correct | 518 ms | 25272 KB | Output is correct |
19 | Correct | 550 ms | 27024 KB | Output is correct |
20 | Correct | 482 ms | 23744 KB | Output is correct |
21 | Correct | 500 ms | 23788 KB | Output is correct |
22 | Correct | 507 ms | 23680 KB | Output is correct |
23 | Correct | 198 ms | 22116 KB | Output is correct |
24 | Correct | 496 ms | 25316 KB | Output is correct |
25 | Correct | 30 ms | 6948 KB | Output is correct |
26 | Correct | 4 ms | 5100 KB | Output is correct |
27 | Correct | 5 ms | 5100 KB | Output is correct |
28 | Correct | 71 ms | 9096 KB | Output is correct |
29 | Correct | 29 ms | 7724 KB | Output is correct |
30 | Correct | 5 ms | 5248 KB | Output is correct |
31 | Correct | 6 ms | 5356 KB | Output is correct |
32 | Correct | 7 ms | 5356 KB | Output is correct |
33 | Correct | 5 ms | 5228 KB | Output is correct |
34 | Correct | 30 ms | 7688 KB | Output is correct |
35 | Correct | 4 ms | 5100 KB | Output is correct |
36 | Correct | 4 ms | 5100 KB | Output is correct |
37 | Correct | 5 ms | 5100 KB | Output is correct |
38 | Correct | 5 ms | 5100 KB | Output is correct |
39 | Correct | 5 ms | 5100 KB | Output is correct |
40 | Correct | 563 ms | 22448 KB | Output is correct |
41 | Correct | 541 ms | 22548 KB | Output is correct |
42 | Correct | 604 ms | 22432 KB | Output is correct |
43 | Correct | 190 ms | 21860 KB | Output is correct |
44 | Correct | 207 ms | 21860 KB | Output is correct |
45 | Correct | 524 ms | 22728 KB | Output is correct |
46 | Correct | 496 ms | 22692 KB | Output is correct |
47 | Correct | 558 ms | 21892 KB | Output is correct |
48 | Correct | 192 ms | 19684 KB | Output is correct |
49 | Correct | 557 ms | 21608 KB | Output is correct |
50 | Correct | 499 ms | 22428 KB | Output is correct |
51 | Correct | 513 ms | 22660 KB | Output is correct |