# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
42116 | 2018-02-22T17:02:59 Z | nonocut | Commuter Pass (JOI18_commuter_pass) | C++14 | 620 ms | 27108 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define X first #define Y second const int maxn = 100005; const ll inf = 1e18; struct node { int x; ll val; node(int _x = 0, ll _val = 0) { x = _x; val = _val; }; bool operator < (node a) const { return a.val<val; } }; int n,m,a,b,c,d; bool vis[maxn]; ll dist[maxn], da[maxn], db[maxn], dc[maxn], dd[maxn]; vector<pair<int,ll>> way[maxn]; priority_queue<node> heap; vector<int> from[maxn]; ll mn[maxn]; ll ans; void sssp(int u) { for(int i=1;i<=n;i++) dist[i] = inf, vis[i] = 0; dist[u] = 0; heap.push(node(u,0)); while(!heap.empty()) { int u = heap.top().x; heap.pop(); if(vis[u]) continue; vis[u] = 1; for(auto t : way[u]) { if(dist[t.X] > dist[u] + t.Y) { dist[t.X] = dist[u] + t.Y; heap.push(node(t.X,dist[t.X])); } } } } void dag(int u) { vis[u] = 1; for(auto t : way[u]) { if(da[t.X] + t.Y == da[u]) { from[t.X].pb(u); if(!vis[t.X]) dag(t.X); } } } void dfs(int u) { vis[u] = 1; mn[u] = dc[u]; for(auto v : from[u]) { if(!vis[v]) dfs(v); mn[u] = min(mn[u], mn[v]); } ans = min(ans, mn[u] + dd[u]); } int main() { scanf("%d%d",&n,&m); scanf("%d%d%d%d",&a,&b,&c,&d); for(int i=0;i<m;i++) { int x,y; ll val; scanf("%d%d%lld",&x,&y,&val); way[x].pb({y,val}); way[y].pb({x,val}); } sssp(a); for(int i=1;i<=n;i++) da[i] = dist[i]; sssp(b); for(int i=1;i<=n;i++) db[i] = dist[i]; sssp(c); for(int i=1;i<=n;i++) dc[i] = dist[i]; sssp(d); for(int i=1;i<=n;i++) dd[i] = dist[i]; for(int i=1;i<=n;i++) vis[i] = 0; dag(b); ans = dc[d]; for(int i=1;i<=n;i++) vis[i] = 0; dfs(a); for(int i=1;i<=n;i++) swap(dc[i], dd[i]); for(int i=1;i<=n;i++) vis[i] = 0; dfs(a); printf("%lld",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 473 ms | 20712 KB | Output is correct |
2 | Correct | 489 ms | 21716 KB | Output is correct |
3 | Correct | 564 ms | 27020 KB | Output is correct |
4 | Correct | 445 ms | 27020 KB | Output is correct |
5 | Correct | 498 ms | 27020 KB | Output is correct |
6 | Correct | 489 ms | 27020 KB | Output is correct |
7 | Correct | 620 ms | 27020 KB | Output is correct |
8 | Correct | 562 ms | 27020 KB | Output is correct |
9 | Correct | 443 ms | 27020 KB | Output is correct |
10 | Correct | 362 ms | 27020 KB | Output is correct |
11 | Correct | 233 ms | 27020 KB | Output is correct |
12 | Correct | 455 ms | 27020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 553 ms | 27020 KB | Output is correct |
2 | Correct | 532 ms | 27020 KB | Output is correct |
3 | Correct | 533 ms | 27020 KB | Output is correct |
4 | Correct | 543 ms | 27020 KB | Output is correct |
5 | Correct | 533 ms | 27020 KB | Output is correct |
6 | Correct | 543 ms | 27020 KB | Output is correct |
7 | Correct | 565 ms | 27108 KB | Output is correct |
8 | Correct | 529 ms | 27108 KB | Output is correct |
9 | Correct | 552 ms | 27108 KB | Output is correct |
10 | Correct | 521 ms | 27108 KB | Output is correct |
11 | Correct | 273 ms | 27108 KB | Output is correct |
12 | Correct | 500 ms | 27108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 27108 KB | Output is correct |
2 | Correct | 6 ms | 27108 KB | Output is correct |
3 | Correct | 6 ms | 27108 KB | Output is correct |
4 | Correct | 28 ms | 27108 KB | Output is correct |
5 | Correct | 17 ms | 27108 KB | Output is correct |
6 | Correct | 6 ms | 27108 KB | Output is correct |
7 | Correct | 7 ms | 27108 KB | Output is correct |
8 | Correct | 7 ms | 27108 KB | Output is correct |
9 | Correct | 6 ms | 27108 KB | Output is correct |
10 | Correct | 16 ms | 27108 KB | Output is correct |
11 | Correct | 6 ms | 27108 KB | Output is correct |
12 | Correct | 6 ms | 27108 KB | Output is correct |
13 | Correct | 6 ms | 27108 KB | Output is correct |
14 | Correct | 7 ms | 27108 KB | Output is correct |
15 | Correct | 7 ms | 27108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 473 ms | 20712 KB | Output is correct |
2 | Correct | 489 ms | 21716 KB | Output is correct |
3 | Correct | 564 ms | 27020 KB | Output is correct |
4 | Correct | 445 ms | 27020 KB | Output is correct |
5 | Correct | 498 ms | 27020 KB | Output is correct |
6 | Correct | 489 ms | 27020 KB | Output is correct |
7 | Correct | 620 ms | 27020 KB | Output is correct |
8 | Correct | 562 ms | 27020 KB | Output is correct |
9 | Correct | 443 ms | 27020 KB | Output is correct |
10 | Correct | 362 ms | 27020 KB | Output is correct |
11 | Correct | 233 ms | 27020 KB | Output is correct |
12 | Correct | 455 ms | 27020 KB | Output is correct |
13 | Correct | 553 ms | 27020 KB | Output is correct |
14 | Correct | 532 ms | 27020 KB | Output is correct |
15 | Correct | 533 ms | 27020 KB | Output is correct |
16 | Correct | 543 ms | 27020 KB | Output is correct |
17 | Correct | 533 ms | 27020 KB | Output is correct |
18 | Correct | 543 ms | 27020 KB | Output is correct |
19 | Correct | 565 ms | 27108 KB | Output is correct |
20 | Correct | 529 ms | 27108 KB | Output is correct |
21 | Correct | 552 ms | 27108 KB | Output is correct |
22 | Correct | 521 ms | 27108 KB | Output is correct |
23 | Correct | 273 ms | 27108 KB | Output is correct |
24 | Correct | 500 ms | 27108 KB | Output is correct |
25 | Correct | 16 ms | 27108 KB | Output is correct |
26 | Correct | 6 ms | 27108 KB | Output is correct |
27 | Correct | 6 ms | 27108 KB | Output is correct |
28 | Correct | 28 ms | 27108 KB | Output is correct |
29 | Correct | 17 ms | 27108 KB | Output is correct |
30 | Correct | 6 ms | 27108 KB | Output is correct |
31 | Correct | 7 ms | 27108 KB | Output is correct |
32 | Correct | 7 ms | 27108 KB | Output is correct |
33 | Correct | 6 ms | 27108 KB | Output is correct |
34 | Correct | 16 ms | 27108 KB | Output is correct |
35 | Correct | 6 ms | 27108 KB | Output is correct |
36 | Correct | 6 ms | 27108 KB | Output is correct |
37 | Correct | 6 ms | 27108 KB | Output is correct |
38 | Correct | 7 ms | 27108 KB | Output is correct |
39 | Correct | 7 ms | 27108 KB | Output is correct |
40 | Correct | 485 ms | 27108 KB | Output is correct |
41 | Correct | 449 ms | 27108 KB | Output is correct |
42 | Correct | 434 ms | 27108 KB | Output is correct |
43 | Correct | 258 ms | 27108 KB | Output is correct |
44 | Correct | 251 ms | 27108 KB | Output is correct |
45 | Correct | 574 ms | 27108 KB | Output is correct |
46 | Correct | 523 ms | 27108 KB | Output is correct |
47 | Correct | 503 ms | 27108 KB | Output is correct |
48 | Correct | 248 ms | 27108 KB | Output is correct |
49 | Correct | 406 ms | 27108 KB | Output is correct |
50 | Correct | 534 ms | 27108 KB | Output is correct |
51 | Correct | 527 ms | 27108 KB | Output is correct |