# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
231468 | 2020-05-13T17:18:45 Z | nafis_shifat | Commuter Pass (JOI18_commuter_pass) | C++14 | 487 ms | 28892 KB |
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> using namespace std; const int mxn=1e5+5; const ll inf=1e18; vector<int> adj[mxn]; vector <ll> cost[mxn]; ll d1[mxn],d2[mxn],d3[mxn],d4[mxn]; ll z; ll ans; int us[mxn]={}; ll minX[mxn],minY[mxn]; void dijkstra(int src,ll dist[]) { for(int i=1;i<mxn;i++)dist[i]=inf; dist[src]=0; priority_queue<pair<ll,int>> pq; pq.push({0,src}); int vis[mxn]={}; while(!pq.empty()) { int u=pq.top().second; pq.pop(); if(vis[u])continue; vis[u]=1; for(int i=0;i<adj[u].size();i++) { int v=adj[u][i]; if(dist[u]+cost[u][i]<dist[v]) { dist[v]=dist[u]+cost[u][i]; pq.push({-dist[v],v}); } } } } void dfs(int cur,ll x,ll y) { x=min(x,d2[cur]); y=min(y,d3[cur]); ans=min(ans,x+y); ans=min(ans,x+minY[cur]); ans=min(ans,y+minX[cur]); if(us[cur])return; us[cur]=1; for(int i=0;i<adj[cur].size();i++) { int v=adj[cur][i]; if(d1[cur]+cost[cur][i]+d4[v]==z) { dfs(v,x,y); minX[cur]=min(minX[cur],minX[v]); minY[cur]=min(minY[cur],minY[v]); } } } int main() { int n,m; scanf("%d%d",&n,&m); int S,T,U,V; scanf("%d%d%d%d",&S,&T,&U,&V); for(int i=0;i<m;i++) { int u,v; ll w; scanf("%d %d %lld",&u,&v,&w); adj[u].push_back(v); adj[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } dijkstra(S,d1); dijkstra(T,d4); dijkstra(U,d2); dijkstra(V,d3); z=d1[T]; ans=d2[V]; for(int i=1;i<=n;i++)minX[i]=d2[i],minY[i]=d3[i]; dfs(S,inf,inf); printf("%lld",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 459 ms | 23484 KB | Output is correct |
2 | Correct | 481 ms | 22480 KB | Output is correct |
3 | Correct | 468 ms | 28892 KB | Output is correct |
4 | Correct | 447 ms | 23544 KB | Output is correct |
5 | Correct | 451 ms | 22568 KB | Output is correct |
6 | Correct | 427 ms | 23472 KB | Output is correct |
7 | Correct | 452 ms | 22468 KB | Output is correct |
8 | Correct | 446 ms | 22432 KB | Output is correct |
9 | Correct | 430 ms | 22172 KB | Output is correct |
10 | Correct | 361 ms | 22128 KB | Output is correct |
11 | Correct | 206 ms | 21132 KB | Output is correct |
12 | Correct | 457 ms | 22140 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 462 ms | 24244 KB | Output is correct |
2 | Correct | 487 ms | 24692 KB | Output is correct |
3 | Correct | 457 ms | 24052 KB | Output is correct |
4 | Correct | 476 ms | 24456 KB | Output is correct |
5 | Correct | 469 ms | 24944 KB | Output is correct |
6 | Correct | 471 ms | 26836 KB | Output is correct |
7 | Correct | 483 ms | 27208 KB | Output is correct |
8 | Correct | 479 ms | 24560 KB | Output is correct |
9 | Correct | 473 ms | 24944 KB | Output is correct |
10 | Correct | 469 ms | 24116 KB | Output is correct |
11 | Correct | 240 ms | 22648 KB | Output is correct |
12 | Correct | 455 ms | 26920 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 9984 KB | Output is correct |
2 | Correct | 9 ms | 8576 KB | Output is correct |
3 | Correct | 10 ms | 8576 KB | Output is correct |
4 | Correct | 31 ms | 11264 KB | Output is correct |
5 | Correct | 19 ms | 9856 KB | Output is correct |
6 | Correct | 10 ms | 8704 KB | Output is correct |
7 | Correct | 10 ms | 8704 KB | Output is correct |
8 | Correct | 11 ms | 8832 KB | Output is correct |
9 | Correct | 10 ms | 8704 KB | Output is correct |
10 | Correct | 20 ms | 9856 KB | Output is correct |
11 | Correct | 9 ms | 8576 KB | Output is correct |
12 | Correct | 9 ms | 8576 KB | Output is correct |
13 | Correct | 9 ms | 8576 KB | Output is correct |
14 | Correct | 9 ms | 8576 KB | Output is correct |
15 | Correct | 10 ms | 8576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 459 ms | 23484 KB | Output is correct |
2 | Correct | 481 ms | 22480 KB | Output is correct |
3 | Correct | 468 ms | 28892 KB | Output is correct |
4 | Correct | 447 ms | 23544 KB | Output is correct |
5 | Correct | 451 ms | 22568 KB | Output is correct |
6 | Correct | 427 ms | 23472 KB | Output is correct |
7 | Correct | 452 ms | 22468 KB | Output is correct |
8 | Correct | 446 ms | 22432 KB | Output is correct |
9 | Correct | 430 ms | 22172 KB | Output is correct |
10 | Correct | 361 ms | 22128 KB | Output is correct |
11 | Correct | 206 ms | 21132 KB | Output is correct |
12 | Correct | 457 ms | 22140 KB | Output is correct |
13 | Correct | 462 ms | 24244 KB | Output is correct |
14 | Correct | 487 ms | 24692 KB | Output is correct |
15 | Correct | 457 ms | 24052 KB | Output is correct |
16 | Correct | 476 ms | 24456 KB | Output is correct |
17 | Correct | 469 ms | 24944 KB | Output is correct |
18 | Correct | 471 ms | 26836 KB | Output is correct |
19 | Correct | 483 ms | 27208 KB | Output is correct |
20 | Correct | 479 ms | 24560 KB | Output is correct |
21 | Correct | 473 ms | 24944 KB | Output is correct |
22 | Correct | 469 ms | 24116 KB | Output is correct |
23 | Correct | 240 ms | 22648 KB | Output is correct |
24 | Correct | 455 ms | 26920 KB | Output is correct |
25 | Correct | 27 ms | 9984 KB | Output is correct |
26 | Correct | 9 ms | 8576 KB | Output is correct |
27 | Correct | 10 ms | 8576 KB | Output is correct |
28 | Correct | 31 ms | 11264 KB | Output is correct |
29 | Correct | 19 ms | 9856 KB | Output is correct |
30 | Correct | 10 ms | 8704 KB | Output is correct |
31 | Correct | 10 ms | 8704 KB | Output is correct |
32 | Correct | 11 ms | 8832 KB | Output is correct |
33 | Correct | 10 ms | 8704 KB | Output is correct |
34 | Correct | 20 ms | 9856 KB | Output is correct |
35 | Correct | 9 ms | 8576 KB | Output is correct |
36 | Correct | 9 ms | 8576 KB | Output is correct |
37 | Correct | 9 ms | 8576 KB | Output is correct |
38 | Correct | 9 ms | 8576 KB | Output is correct |
39 | Correct | 10 ms | 8576 KB | Output is correct |
40 | Correct | 421 ms | 25972 KB | Output is correct |
41 | Correct | 452 ms | 25096 KB | Output is correct |
42 | Correct | 466 ms | 25248 KB | Output is correct |
43 | Correct | 229 ms | 22396 KB | Output is correct |
44 | Correct | 221 ms | 22392 KB | Output is correct |
45 | Correct | 449 ms | 25248 KB | Output is correct |
46 | Correct | 445 ms | 24292 KB | Output is correct |
47 | Correct | 459 ms | 25864 KB | Output is correct |
48 | Correct | 219 ms | 19196 KB | Output is correct |
49 | Correct | 362 ms | 25588 KB | Output is correct |
50 | Correct | 425 ms | 24440 KB | Output is correct |
51 | Correct | 434 ms | 24488 KB | Output is correct |