#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
int n,m;
int s,t,u,v;
vector<ii> adj[100005];
ll dist[4][100005];
ll minsofar[2][100005];
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
void dijkstra(int idx,int source){
for(int i=0;i<n;i++)dist[idx][i]=LLINF;
dist[idx][source]=0;
pq.push(mp(0,source));
while(!pq.empty()){
pair<ll,int> cur=pq.top();pq.pop();
for(ii i:adj[cur.se]){
if(dist[idx][i.fi]>dist[idx][cur.se]+i.se){
dist[idx][i.fi]=dist[idx][cur.se]+i.se;
pq.push(mp(dist[idx][i.fi],i.fi));
}
}
}
}
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);s--;t--;u--;v--;
int a,b,c;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);a--;b--;
adj[a].pb(b,c);
adj[b].pb(a,c);
}
dijkstra(0,u);
dijkstra(1,v);
dijkstra(2,s);
ll ans=LLINF;
for(int i=0;i<n;i++){
dist[3][i]=LLINF;
minsofar[0][i]=dist[0][i];
minsofar[1][i]=dist[1][i];
}
dist[3][t]=0;
pq.push(mp(0,t));
while(!pq.empty()){
pair<ll,int> cur=pq.top();pq.pop();
for(ii i:adj[cur.se]){
if(dist[3][i.fi]>dist[3][cur.se]+i.se){
dist[3][i.fi]=dist[3][cur.se]+i.se;
for(int j=0;j<2;j++)minsofar[j][i.fi]=min(minsofar[j][cur.se],dist[j][i.fi]);
pq.push(mp(dist[3][i.fi],i.fi));
}else if(dist[3][i.fi]==dist[3][cur.se]+i.se){
for(int j=0;j<2;j++)minsofar[j][i.fi]=min(minsofar[j][cur.se],minsofar[j][i.fi]);
}
}
}
for(int i=0;i<n;i++){
if(dist[2][i]+dist[3][i]==dist[2][t]){
ans=min(ans,minsofar[0][i]+dist[1][i]);
ans=min(ans,minsofar[1][i]+dist[0][i]);
}
}
printf("%lld",min(ans,dist[0][v]));
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);s--;t--;u--;v--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d%d%d",&a,&b,&c);a--;b--;
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
376 ms |
14960 KB |
Output is correct |
2 |
Correct |
361 ms |
14904 KB |
Output is correct |
3 |
Correct |
406 ms |
19408 KB |
Output is correct |
4 |
Correct |
328 ms |
18592 KB |
Output is correct |
5 |
Correct |
326 ms |
17920 KB |
Output is correct |
6 |
Correct |
368 ms |
18716 KB |
Output is correct |
7 |
Correct |
380 ms |
18004 KB |
Output is correct |
8 |
Correct |
362 ms |
18112 KB |
Output is correct |
9 |
Correct |
337 ms |
18812 KB |
Output is correct |
10 |
Correct |
297 ms |
18808 KB |
Output is correct |
11 |
Correct |
132 ms |
12472 KB |
Output is correct |
12 |
Correct |
397 ms |
18724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
365 ms |
14952 KB |
Output is correct |
2 |
Correct |
483 ms |
14900 KB |
Output is correct |
3 |
Correct |
365 ms |
17976 KB |
Output is correct |
4 |
Correct |
405 ms |
18024 KB |
Output is correct |
5 |
Correct |
421 ms |
18052 KB |
Output is correct |
6 |
Correct |
339 ms |
18348 KB |
Output is correct |
7 |
Correct |
344 ms |
17932 KB |
Output is correct |
8 |
Correct |
398 ms |
18048 KB |
Output is correct |
9 |
Correct |
518 ms |
17980 KB |
Output is correct |
10 |
Correct |
430 ms |
18108 KB |
Output is correct |
11 |
Correct |
169 ms |
12484 KB |
Output is correct |
12 |
Correct |
352 ms |
18376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
3668 KB |
Output is correct |
2 |
Correct |
2 ms |
2676 KB |
Output is correct |
3 |
Correct |
3 ms |
2660 KB |
Output is correct |
4 |
Correct |
19 ms |
4292 KB |
Output is correct |
5 |
Correct |
14 ms |
3584 KB |
Output is correct |
6 |
Correct |
3 ms |
2772 KB |
Output is correct |
7 |
Correct |
3 ms |
2772 KB |
Output is correct |
8 |
Correct |
5 ms |
2772 KB |
Output is correct |
9 |
Correct |
3 ms |
2784 KB |
Output is correct |
10 |
Correct |
9 ms |
3548 KB |
Output is correct |
11 |
Correct |
2 ms |
2656 KB |
Output is correct |
12 |
Correct |
3 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2660 KB |
Output is correct |
15 |
Correct |
4 ms |
2668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
376 ms |
14960 KB |
Output is correct |
2 |
Correct |
361 ms |
14904 KB |
Output is correct |
3 |
Correct |
406 ms |
19408 KB |
Output is correct |
4 |
Correct |
328 ms |
18592 KB |
Output is correct |
5 |
Correct |
326 ms |
17920 KB |
Output is correct |
6 |
Correct |
368 ms |
18716 KB |
Output is correct |
7 |
Correct |
380 ms |
18004 KB |
Output is correct |
8 |
Correct |
362 ms |
18112 KB |
Output is correct |
9 |
Correct |
337 ms |
18812 KB |
Output is correct |
10 |
Correct |
297 ms |
18808 KB |
Output is correct |
11 |
Correct |
132 ms |
12472 KB |
Output is correct |
12 |
Correct |
397 ms |
18724 KB |
Output is correct |
13 |
Correct |
365 ms |
14952 KB |
Output is correct |
14 |
Correct |
483 ms |
14900 KB |
Output is correct |
15 |
Correct |
365 ms |
17976 KB |
Output is correct |
16 |
Correct |
405 ms |
18024 KB |
Output is correct |
17 |
Correct |
421 ms |
18052 KB |
Output is correct |
18 |
Correct |
339 ms |
18348 KB |
Output is correct |
19 |
Correct |
344 ms |
17932 KB |
Output is correct |
20 |
Correct |
398 ms |
18048 KB |
Output is correct |
21 |
Correct |
518 ms |
17980 KB |
Output is correct |
22 |
Correct |
430 ms |
18108 KB |
Output is correct |
23 |
Correct |
169 ms |
12484 KB |
Output is correct |
24 |
Correct |
352 ms |
18376 KB |
Output is correct |
25 |
Correct |
14 ms |
3668 KB |
Output is correct |
26 |
Correct |
2 ms |
2676 KB |
Output is correct |
27 |
Correct |
3 ms |
2660 KB |
Output is correct |
28 |
Correct |
19 ms |
4292 KB |
Output is correct |
29 |
Correct |
14 ms |
3584 KB |
Output is correct |
30 |
Correct |
3 ms |
2772 KB |
Output is correct |
31 |
Correct |
3 ms |
2772 KB |
Output is correct |
32 |
Correct |
5 ms |
2772 KB |
Output is correct |
33 |
Correct |
3 ms |
2784 KB |
Output is correct |
34 |
Correct |
9 ms |
3548 KB |
Output is correct |
35 |
Correct |
2 ms |
2656 KB |
Output is correct |
36 |
Correct |
3 ms |
2644 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
2 ms |
2660 KB |
Output is correct |
39 |
Correct |
4 ms |
2668 KB |
Output is correct |
40 |
Correct |
324 ms |
19028 KB |
Output is correct |
41 |
Correct |
337 ms |
18892 KB |
Output is correct |
42 |
Correct |
358 ms |
18788 KB |
Output is correct |
43 |
Correct |
145 ms |
12572 KB |
Output is correct |
44 |
Correct |
129 ms |
12488 KB |
Output is correct |
45 |
Correct |
290 ms |
17668 KB |
Output is correct |
46 |
Correct |
292 ms |
17420 KB |
Output is correct |
47 |
Correct |
393 ms |
18552 KB |
Output is correct |
48 |
Correct |
134 ms |
11992 KB |
Output is correct |
49 |
Correct |
245 ms |
18616 KB |
Output is correct |
50 |
Correct |
329 ms |
17788 KB |
Output is correct |
51 |
Correct |
296 ms |
17592 KB |
Output is correct |