#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define ip pair<int,ii>
#define fi first
#define se second
const int maxn=1e5+7;
const int inf=1e15+7;
int vst[maxn];
int du[maxn];
int dv[maxn];
int ds[maxn];
int n,m,s,t,u,v;
int ans;
vector<ii>a[maxn];
int d[2][maxn];
void dijkstra1(int start,int arr[])
{
for(int i=1;i<=n;i++){vst[i]=0;arr[i]=inf;}
priority_queue<ii,vector<ii>,greater<ii>>q;
arr[start]=0;
q.push({0,start});
while(q.size()){
int u=q.top().se;
int du=q.top().fi;
q.pop();
if(vst[u])continue;
vst[u]=1;
for(ii p:a[u]){
int v=p.fi;
int w=p.se;
if(arr[v]>arr[u]+w){
arr[v]=arr[u]+w;
q.push({arr[v],v});
}
}
}
}
void dijkstra2(int start,int endd)
{
for(int i=0;i<=n;i++){
d[0][i]=inf;
d[1][i]=inf;
ds[i]=inf;
vst[i]=0;
}
ds[start]=0;
priority_queue<ip,vector<ip>,greater<ip>>q;
q.push(make_pair(0,make_pair(start,0)));
while(q.size()){
int node=q.top().se.fi;
int par=q.top().se.se;
int dnode=q.top().fi;
q.pop();
if(vst[node]==0){
vst[node]=1;
d[0][node]=min(du[node],d[0][par]);
d[1][node]=min(dv[node],d[1][par]);
ds[node]=dnode;
for(ii p:a[node]){
int v=p.fi;
int w=p.se;
q.push(make_pair(dnode+w,make_pair(v,node)));
}
}
else if(dnode==ds[node]){
if(min(du[node],d[0][par])+min(dv[node],d[1][par])<=d[0][node]+d[1][node])
{
d[0][node]=min(d[0][par],du[node]);
d[1][node]=min(d[1][par],dv[node]);
}
}
}
ans=min(ans,d[0][endd]+d[1][endd]);
}
main()
{
cin>>n>>m;
cin>>s>>t;
cin>>u>>v;
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
a[x].push_back({y,w});
a[y].push_back({x,w});
}
dijkstra1(u,du);
dijkstra1(v,dv);
ans=du[v];
dijkstra2(s,t);
dijkstra2(t,s);
cout<<ans;
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:27:13: warning: unused variable 'du' [-Wunused-variable]
27 | int du=q.top().fi;
| ^~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
80 | main()
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
439 ms |
29700 KB |
Output is correct |
2 |
Correct |
378 ms |
28168 KB |
Output is correct |
3 |
Correct |
373 ms |
28068 KB |
Output is correct |
4 |
Correct |
460 ms |
28276 KB |
Output is correct |
5 |
Correct |
373 ms |
23688 KB |
Output is correct |
6 |
Correct |
407 ms |
29744 KB |
Output is correct |
7 |
Correct |
457 ms |
28580 KB |
Output is correct |
8 |
Correct |
387 ms |
32020 KB |
Output is correct |
9 |
Correct |
424 ms |
33732 KB |
Output is correct |
10 |
Correct |
432 ms |
32280 KB |
Output is correct |
11 |
Correct |
136 ms |
14536 KB |
Output is correct |
12 |
Correct |
416 ms |
32440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
424 ms |
29028 KB |
Output is correct |
2 |
Correct |
388 ms |
23852 KB |
Output is correct |
3 |
Correct |
441 ms |
27580 KB |
Output is correct |
4 |
Correct |
395 ms |
23772 KB |
Output is correct |
5 |
Correct |
438 ms |
23708 KB |
Output is correct |
6 |
Correct |
414 ms |
27320 KB |
Output is correct |
7 |
Correct |
366 ms |
23656 KB |
Output is correct |
8 |
Correct |
423 ms |
24216 KB |
Output is correct |
9 |
Correct |
394 ms |
23964 KB |
Output is correct |
10 |
Correct |
395 ms |
28636 KB |
Output is correct |
11 |
Correct |
144 ms |
12632 KB |
Output is correct |
12 |
Correct |
402 ms |
27712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
9016 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
2 ms |
6660 KB |
Output is correct |
4 |
Correct |
58 ms |
12284 KB |
Output is correct |
5 |
Correct |
29 ms |
10636 KB |
Output is correct |
6 |
Correct |
4 ms |
6752 KB |
Output is correct |
7 |
Correct |
5 ms |
6744 KB |
Output is correct |
8 |
Correct |
5 ms |
7004 KB |
Output is correct |
9 |
Correct |
3 ms |
6792 KB |
Output is correct |
10 |
Correct |
28 ms |
10504 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
2 ms |
6492 KB |
Output is correct |
15 |
Correct |
2 ms |
7256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
439 ms |
29700 KB |
Output is correct |
2 |
Correct |
378 ms |
28168 KB |
Output is correct |
3 |
Correct |
373 ms |
28068 KB |
Output is correct |
4 |
Correct |
460 ms |
28276 KB |
Output is correct |
5 |
Correct |
373 ms |
23688 KB |
Output is correct |
6 |
Correct |
407 ms |
29744 KB |
Output is correct |
7 |
Correct |
457 ms |
28580 KB |
Output is correct |
8 |
Correct |
387 ms |
32020 KB |
Output is correct |
9 |
Correct |
424 ms |
33732 KB |
Output is correct |
10 |
Correct |
432 ms |
32280 KB |
Output is correct |
11 |
Correct |
136 ms |
14536 KB |
Output is correct |
12 |
Correct |
416 ms |
32440 KB |
Output is correct |
13 |
Correct |
424 ms |
29028 KB |
Output is correct |
14 |
Correct |
388 ms |
23852 KB |
Output is correct |
15 |
Correct |
441 ms |
27580 KB |
Output is correct |
16 |
Correct |
395 ms |
23772 KB |
Output is correct |
17 |
Correct |
438 ms |
23708 KB |
Output is correct |
18 |
Correct |
414 ms |
27320 KB |
Output is correct |
19 |
Correct |
366 ms |
23656 KB |
Output is correct |
20 |
Correct |
423 ms |
24216 KB |
Output is correct |
21 |
Correct |
394 ms |
23964 KB |
Output is correct |
22 |
Correct |
395 ms |
28636 KB |
Output is correct |
23 |
Correct |
144 ms |
12632 KB |
Output is correct |
24 |
Correct |
402 ms |
27712 KB |
Output is correct |
25 |
Correct |
28 ms |
9016 KB |
Output is correct |
26 |
Correct |
2 ms |
6492 KB |
Output is correct |
27 |
Correct |
2 ms |
6660 KB |
Output is correct |
28 |
Correct |
58 ms |
12284 KB |
Output is correct |
29 |
Correct |
29 ms |
10636 KB |
Output is correct |
30 |
Correct |
4 ms |
6752 KB |
Output is correct |
31 |
Correct |
5 ms |
6744 KB |
Output is correct |
32 |
Correct |
5 ms |
7004 KB |
Output is correct |
33 |
Correct |
3 ms |
6792 KB |
Output is correct |
34 |
Correct |
28 ms |
10504 KB |
Output is correct |
35 |
Correct |
2 ms |
6492 KB |
Output is correct |
36 |
Correct |
2 ms |
6492 KB |
Output is correct |
37 |
Correct |
2 ms |
6492 KB |
Output is correct |
38 |
Correct |
2 ms |
6492 KB |
Output is correct |
39 |
Correct |
2 ms |
7256 KB |
Output is correct |
40 |
Correct |
392 ms |
32244 KB |
Output is correct |
41 |
Correct |
443 ms |
33692 KB |
Output is correct |
42 |
Correct |
449 ms |
33916 KB |
Output is correct |
43 |
Correct |
125 ms |
14612 KB |
Output is correct |
44 |
Correct |
143 ms |
14672 KB |
Output is correct |
45 |
Correct |
378 ms |
26212 KB |
Output is correct |
46 |
Correct |
377 ms |
26900 KB |
Output is correct |
47 |
Correct |
418 ms |
27744 KB |
Output is correct |
48 |
Correct |
108 ms |
14192 KB |
Output is correct |
49 |
Correct |
379 ms |
32052 KB |
Output is correct |
50 |
Correct |
360 ms |
26284 KB |
Output is correct |
51 |
Correct |
357 ms |
27224 KB |
Output is correct |