# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
66739 | 2018-08-12T08:28:44 Z | yusufake | Commuter Pass (JOI18_commuter_pass) | C++ | 908 ms | 196692 KB |
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define st first #define nd second typedef long long ll; typedef pair < int , int > pp; const int mod = 1e9 + 7; const int N = 5e5 + 5; priority_queue < pair < ll , pp > > Q; vector < pp > V[N]; vector < int > Y[N],Z[N]; ll D[N][3],H[N][3],T[N],TT[N],M[N],MM[N],n,m,i,x,y,z,a,b,c,d,ans; void f(int x, int h){ while(Q.size()) Q.pop(); ll p,u; Q.push(mp(0,mp(x,0))); for(; Q.size() ;){ x = Q.top().nd.st; p = Q.top().nd.nd; u = Q.top().st; Q.pop(); if(H[x][h]){ if(!h && D[x][h] == -u){ Y[p].pb(x); Z[x].pb(p); } continue; } H[x][h] = 1; D[x][h] = -u; if(!h) Y[p].pb(x); if(!h) Z[x].pb(p); for(auto t : V[x]){ Q.push(mp(u-t.nd,mp(t.st,x))); } } } void g(int x){ T[x] = 1; for(auto y : Z[x]) if(!T[y]) g(y); } void gg(int x){ TT[x] = 1; M[x] = D[x][1]; MM[x] = D[x][2]; for(auto y : Y[x]){ if(!T[y]) continue; if(!TT[y]) gg(y); M[x] = min(M[x] , M[y]); MM[x] = min(MM[x] , MM[y]); } //cout << x << " ss\n"; ans = min(ans , D[x][2] + M[x]); ans = min(ans , D[x][1] + MM[x]); } int main(){ scanf("%d%d",&n,&m); scanf("%d%d",&a,&b); scanf("%d%d",&c,&d); for(i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); V[x].pb(mp(y,z)); V[y].pb(mp(x,z)); } memset(D , 22 , sizeof D); f(a,0); f(c,1); f(d,2); //cout << b << " " << Z[b].size() << " aa\n"; g(b); //for(i=1;i<=n;i++) printf("%d ",T[i]); puts(""); ans = D[d][1]; gg(a); printf("%lld",ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 908 ms | 67252 KB | Output is correct |
2 | Correct | 820 ms | 74200 KB | Output is correct |
3 | Correct | 889 ms | 81284 KB | Output is correct |
4 | Correct | 902 ms | 81284 KB | Output is correct |
5 | Correct | 734 ms | 87684 KB | Output is correct |
6 | Correct | 826 ms | 87684 KB | Output is correct |
7 | Correct | 760 ms | 96548 KB | Output is correct |
8 | Correct | 687 ms | 99260 KB | Output is correct |
9 | Correct | 742 ms | 99260 KB | Output is correct |
10 | Correct | 781 ms | 101568 KB | Output is correct |
11 | Correct | 311 ms | 104704 KB | Output is correct |
12 | Correct | 756 ms | 109144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 862 ms | 115980 KB | Output is correct |
2 | Correct | 799 ms | 119488 KB | Output is correct |
3 | Correct | 799 ms | 122760 KB | Output is correct |
4 | Correct | 787 ms | 126304 KB | Output is correct |
5 | Correct | 817 ms | 129956 KB | Output is correct |
6 | Correct | 859 ms | 135760 KB | Output is correct |
7 | Correct | 824 ms | 139532 KB | Output is correct |
8 | Correct | 742 ms | 140172 KB | Output is correct |
9 | Correct | 766 ms | 144548 KB | Output is correct |
10 | Correct | 792 ms | 147032 KB | Output is correct |
11 | Correct | 328 ms | 147084 KB | Output is correct |
12 | Correct | 803 ms | 155536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 155536 KB | Output is correct |
2 | Correct | 46 ms | 155536 KB | Output is correct |
3 | Correct | 44 ms | 155536 KB | Output is correct |
4 | Correct | 127 ms | 155536 KB | Output is correct |
5 | Correct | 88 ms | 155536 KB | Output is correct |
6 | Correct | 47 ms | 155536 KB | Output is correct |
7 | Correct | 52 ms | 155536 KB | Output is correct |
8 | Correct | 53 ms | 155536 KB | Output is correct |
9 | Correct | 47 ms | 155536 KB | Output is correct |
10 | Correct | 78 ms | 155536 KB | Output is correct |
11 | Correct | 47 ms | 155536 KB | Output is correct |
12 | Correct | 43 ms | 155536 KB | Output is correct |
13 | Correct | 47 ms | 155536 KB | Output is correct |
14 | Correct | 44 ms | 155536 KB | Output is correct |
15 | Correct | 49 ms | 155536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 908 ms | 67252 KB | Output is correct |
2 | Correct | 820 ms | 74200 KB | Output is correct |
3 | Correct | 889 ms | 81284 KB | Output is correct |
4 | Correct | 902 ms | 81284 KB | Output is correct |
5 | Correct | 734 ms | 87684 KB | Output is correct |
6 | Correct | 826 ms | 87684 KB | Output is correct |
7 | Correct | 760 ms | 96548 KB | Output is correct |
8 | Correct | 687 ms | 99260 KB | Output is correct |
9 | Correct | 742 ms | 99260 KB | Output is correct |
10 | Correct | 781 ms | 101568 KB | Output is correct |
11 | Correct | 311 ms | 104704 KB | Output is correct |
12 | Correct | 756 ms | 109144 KB | Output is correct |
13 | Correct | 862 ms | 115980 KB | Output is correct |
14 | Correct | 799 ms | 119488 KB | Output is correct |
15 | Correct | 799 ms | 122760 KB | Output is correct |
16 | Correct | 787 ms | 126304 KB | Output is correct |
17 | Correct | 817 ms | 129956 KB | Output is correct |
18 | Correct | 859 ms | 135760 KB | Output is correct |
19 | Correct | 824 ms | 139532 KB | Output is correct |
20 | Correct | 742 ms | 140172 KB | Output is correct |
21 | Correct | 766 ms | 144548 KB | Output is correct |
22 | Correct | 792 ms | 147032 KB | Output is correct |
23 | Correct | 328 ms | 147084 KB | Output is correct |
24 | Correct | 803 ms | 155536 KB | Output is correct |
25 | Correct | 87 ms | 155536 KB | Output is correct |
26 | Correct | 46 ms | 155536 KB | Output is correct |
27 | Correct | 44 ms | 155536 KB | Output is correct |
28 | Correct | 127 ms | 155536 KB | Output is correct |
29 | Correct | 88 ms | 155536 KB | Output is correct |
30 | Correct | 47 ms | 155536 KB | Output is correct |
31 | Correct | 52 ms | 155536 KB | Output is correct |
32 | Correct | 53 ms | 155536 KB | Output is correct |
33 | Correct | 47 ms | 155536 KB | Output is correct |
34 | Correct | 78 ms | 155536 KB | Output is correct |
35 | Correct | 47 ms | 155536 KB | Output is correct |
36 | Correct | 43 ms | 155536 KB | Output is correct |
37 | Correct | 47 ms | 155536 KB | Output is correct |
38 | Correct | 44 ms | 155536 KB | Output is correct |
39 | Correct | 49 ms | 155536 KB | Output is correct |
40 | Correct | 748 ms | 155536 KB | Output is correct |
41 | Correct | 772 ms | 159488 KB | Output is correct |
42 | Correct | 840 ms | 163792 KB | Output is correct |
43 | Correct | 401 ms | 167228 KB | Output is correct |
44 | Correct | 382 ms | 169496 KB | Output is correct |
45 | Correct | 832 ms | 176464 KB | Output is correct |
46 | Correct | 835 ms | 179520 KB | Output is correct |
47 | Correct | 821 ms | 179520 KB | Output is correct |
48 | Correct | 405 ms | 180996 KB | Output is correct |
49 | Correct | 872 ms | 182732 KB | Output is correct |
50 | Correct | 775 ms | 189036 KB | Output is correct |
51 | Correct | 832 ms | 196692 KB | Output is correct |