# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
268253 | 2020-08-16T10:45:34 Z | MKopchev | Commuter Pass (JOI18_commuter_pass) | C++14 | 719 ms | 24412 KB |
#include<bits/stdc++.h> using namespace std; const int nmax=1e5+42; int n,m; vector< pair<int/*to*/,int/*cost*/> > adj[nmax]; int s,t; int u,v; long long dist[4][nmax];//from s, from t, from u, from v priority_queue< pair<long long/*dist*/,int/*node*/> > pq; void dij(int node,int id) { pq.push({0,node}); while(pq.size()) { pair<long long/*dist*/,int/*node*/> tp=pq.top(); pq.pop(); tp.first=-tp.first; //cout<<tp.first<<" "<<tp.second<<endl; if(dist[id][tp.second]!=-1)continue; dist[id][tp.second]=tp.first; for(auto k:adj[tp.second]) { pq.push({-(tp.first+k.second),k.first}); //cout<<"edge "<<k.first<<" "<<k.second<<endl; } } /* cout<<id<<endl; for(int i=1;i<=n;i++)cout<<dist[id][i]<<" ";cout<<endl; */ } long long mini[nmax]; bool been[nmax]; vector<int> dag_edges[nmax]; int OTHER; long long find_mini(int node) { if(been[node])return mini[node]; mini[node]=dist[OTHER][node]; for(auto k:dag_edges[node]) { mini[node]=min(mini[node],find_mini(k)); } been[node]=1; return mini[node]; } long long solve(int original,int other) { //cout<<original<<" "<<other<<" : "<<endl; OTHER=other; memset(been,0,sizeof(been)); for(int i=1;i<=n;i++)mini[i]=1e18; for(int i=1;i<=n;i++)dag_edges[i]={}; for(int i=1;i<=n;i++) for(auto k:adj[i]) if(dist[0][i]+k.second+dist[1][k.first]==dist[0][t]&&dist[0][i]<dist[0][k.first]) { //cout<<i<<" -> "<<k.first<<endl; dag_edges[i].push_back(k.first); } /* cout<<"find mini"<<endl; for(int i=1;i<=n;i++)cout<<i<<" -> "<<find_mini(i)<<endl; */ long long ret=1e18; for(int i=1;i<=n;i++) { long long cur=dist[original][i]; cur=cur+find_mini(i); //cout<<i<<" -> "<<cur<<" "<<dist[original][i]<<" "<<find_mini(i)<<endl; ret=min(ret,cur); } //cout<<"ret= "<<ret<<endl; return ret; } int main() { memset(dist,-1,sizeof(dist)); scanf("%i%i",&n,&m); scanf("%i%i",&s,&t); scanf("%i%i",&u,&v); for(int i=1;i<=m;i++) { int a,b,c; scanf("%i%i%i",&a,&b,&c); adj[a].push_back({b,c}); adj[b].push_back({a,c}); } dij(s,0); dij(t,1); dij(u,2); dij(v,3); long long outp=dist[3][u]; outp=min(outp,solve(3,2)); outp=min(outp,solve(2,3)); printf("%lld\n",outp); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 708 ms | 22524 KB | Output is correct |
2 | Correct | 549 ms | 22116 KB | Output is correct |
3 | Correct | 563 ms | 24048 KB | Output is correct |
4 | Correct | 581 ms | 22500 KB | Output is correct |
5 | Correct | 571 ms | 21836 KB | Output is correct |
6 | Correct | 719 ms | 22704 KB | Output is correct |
7 | Correct | 644 ms | 22788 KB | Output is correct |
8 | Correct | 605 ms | 22480 KB | Output is correct |
9 | Correct | 638 ms | 23144 KB | Output is correct |
10 | Correct | 585 ms | 23140 KB | Output is correct |
11 | Correct | 194 ms | 16632 KB | Output is correct |
12 | Correct | 612 ms | 22848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 654 ms | 22372 KB | Output is correct |
2 | Correct | 585 ms | 22244 KB | Output is correct |
3 | Correct | 541 ms | 22244 KB | Output is correct |
4 | Correct | 533 ms | 21860 KB | Output is correct |
5 | Correct | 514 ms | 21860 KB | Output is correct |
6 | Correct | 538 ms | 23900 KB | Output is correct |
7 | Correct | 562 ms | 24040 KB | Output is correct |
8 | Correct | 558 ms | 21792 KB | Output is correct |
9 | Correct | 530 ms | 22400 KB | Output is correct |
10 | Correct | 524 ms | 22148 KB | Output is correct |
11 | Correct | 181 ms | 17784 KB | Output is correct |
12 | Correct | 573 ms | 24412 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 9852 KB | Output is correct |
2 | Correct | 6 ms | 8320 KB | Output is correct |
3 | Correct | 6 ms | 8320 KB | Output is correct |
4 | Correct | 79 ms | 11376 KB | Output is correct |
5 | Correct | 44 ms | 10360 KB | Output is correct |
6 | Correct | 8 ms | 8320 KB | Output is correct |
7 | Correct | 10 ms | 8448 KB | Output is correct |
8 | Correct | 11 ms | 8576 KB | Output is correct |
9 | Correct | 8 ms | 8320 KB | Output is correct |
10 | Correct | 43 ms | 10368 KB | Output is correct |
11 | Correct | 6 ms | 8320 KB | Output is correct |
12 | Correct | 6 ms | 8320 KB | Output is correct |
13 | Correct | 7 ms | 8320 KB | Output is correct |
14 | Correct | 7 ms | 8320 KB | Output is correct |
15 | Correct | 7 ms | 8320 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 708 ms | 22524 KB | Output is correct |
2 | Correct | 549 ms | 22116 KB | Output is correct |
3 | Correct | 563 ms | 24048 KB | Output is correct |
4 | Correct | 581 ms | 22500 KB | Output is correct |
5 | Correct | 571 ms | 21836 KB | Output is correct |
6 | Correct | 719 ms | 22704 KB | Output is correct |
7 | Correct | 644 ms | 22788 KB | Output is correct |
8 | Correct | 605 ms | 22480 KB | Output is correct |
9 | Correct | 638 ms | 23144 KB | Output is correct |
10 | Correct | 585 ms | 23140 KB | Output is correct |
11 | Correct | 194 ms | 16632 KB | Output is correct |
12 | Correct | 612 ms | 22848 KB | Output is correct |
13 | Correct | 654 ms | 22372 KB | Output is correct |
14 | Correct | 585 ms | 22244 KB | Output is correct |
15 | Correct | 541 ms | 22244 KB | Output is correct |
16 | Correct | 533 ms | 21860 KB | Output is correct |
17 | Correct | 514 ms | 21860 KB | Output is correct |
18 | Correct | 538 ms | 23900 KB | Output is correct |
19 | Correct | 562 ms | 24040 KB | Output is correct |
20 | Correct | 558 ms | 21792 KB | Output is correct |
21 | Correct | 530 ms | 22400 KB | Output is correct |
22 | Correct | 524 ms | 22148 KB | Output is correct |
23 | Correct | 181 ms | 17784 KB | Output is correct |
24 | Correct | 573 ms | 24412 KB | Output is correct |
25 | Correct | 42 ms | 9852 KB | Output is correct |
26 | Correct | 6 ms | 8320 KB | Output is correct |
27 | Correct | 6 ms | 8320 KB | Output is correct |
28 | Correct | 79 ms | 11376 KB | Output is correct |
29 | Correct | 44 ms | 10360 KB | Output is correct |
30 | Correct | 8 ms | 8320 KB | Output is correct |
31 | Correct | 10 ms | 8448 KB | Output is correct |
32 | Correct | 11 ms | 8576 KB | Output is correct |
33 | Correct | 8 ms | 8320 KB | Output is correct |
34 | Correct | 43 ms | 10368 KB | Output is correct |
35 | Correct | 6 ms | 8320 KB | Output is correct |
36 | Correct | 6 ms | 8320 KB | Output is correct |
37 | Correct | 7 ms | 8320 KB | Output is correct |
38 | Correct | 7 ms | 8320 KB | Output is correct |
39 | Correct | 7 ms | 8320 KB | Output is correct |
40 | Correct | 629 ms | 22544 KB | Output is correct |
41 | Correct | 641 ms | 22884 KB | Output is correct |
42 | Correct | 601 ms | 22884 KB | Output is correct |
43 | Correct | 237 ms | 18808 KB | Output is correct |
44 | Correct | 226 ms | 18936 KB | Output is correct |
45 | Correct | 627 ms | 22628 KB | Output is correct |
46 | Correct | 639 ms | 22244 KB | Output is correct |
47 | Correct | 601 ms | 21040 KB | Output is correct |
48 | Correct | 235 ms | 17432 KB | Output is correct |
49 | Correct | 636 ms | 22128 KB | Output is correct |
50 | Correct | 637 ms | 21900 KB | Output is correct |
51 | Correct | 625 ms | 22640 KB | Output is correct |