#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define INF 10000000000000000
int n,m,s,t,u,v;
vector<pii> nei[1000000];
vector<int> tree[1000000];
lld dist[1000000];
priority_queue<pii> pq;
void calc(int init){
rep(i,0,n)dist[i]=INF;
dist[init]=0;
pq.push(pii(0,init));
while(!pq.empty()){
int u=pq.top().second;
lld d=-pq.top().first;
pq.pop();
if(d>dist[u])continue;
//cout<<u<<" "<<d<<endl;
trav(V,nei[u]){
//cout<<v.first<<"A"<<v.second<<" "<<d<<" "<<dist[v.first]<<endl;
if(dist[V.first]>V.second+d){
dist[V.first]=V.second+d;
pq.push(pii(-dist[V.first],V.first));
}
}
}
}
bool visited[1000000];
void Rev(int node){
visited[node]=true;
trav(V,nei[node]){
if(dist[V.first]+V.second==dist[node]){
tree[node].push_back(V.first);
if(!visited[V.first])Rev(V.first);
}
}
}
lld dist_u[1000000];
lld dist_v[1000000];
lld min_dist_u[1000000];
lld min_dist_v[1000000];
lld calc_u(int node){
if(min_dist_u[node]!=-1)return min_dist_u[node];
min_dist_u[node]=dist_u[node];
trav(V,tree[node]){
min_dist_u[node]=min(min_dist_u[node],calc_u(V));
}
return min_dist_u[node];
}
lld calc_v(int node){
if(min_dist_v[node]!=-1)return min_dist_v[node];
min_dist_v[node]=dist_v[node];
trav(V,tree[node]){
min_dist_v[node]=min(min_dist_v[node],calc_v(V));
}
return min_dist_v[node];
}
int main(){
scanf("%d %d",&n,&m);
scanf("%d %d",&s,&t);
s--;t--;
scanf("%d %d",&u,&v);
u--;v--;
rep(i,0,m){
int x,y;
lld c;
scanf("%d %d %lld",&x,&y,&c);
x--;y--;
nei[x].push_back(pii(y,c));
nei[y].push_back(pii(x,c));
}
calc(s);
//rep(i,0,n)cout<<dist[i]<<endl;
rep(i,0,n){
visited[i]=false;
}
Rev(t);
/*rep(i,0,n){
trav(v,tree[i])cout<<v<<" ";
cout<<endl;
}*/
calc(u);
rep(i,0,n){
dist_u[i]=dist[i];
min_dist_u[i]=-1;
}
calc(v);
rep(i,0,n){
dist_v[i]=dist[i];
min_dist_v[i]=-1;
}
lld ans=dist_u[v];
rep(i,0,n){
if(visited[i]){
calc_u(i);
calc_v(i);
ans=min(ans,dist_v[i]+min_dist_u[i]);
ans=min(ans,dist_u[i]+min_dist_v[i]);
}
}
printf("%lld\n",ans);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&s,&t);
~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&u,&v);
~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&x,&y,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
390 ms |
63212 KB |
Output is correct |
2 |
Correct |
427 ms |
63360 KB |
Output is correct |
3 |
Correct |
563 ms |
69356 KB |
Output is correct |
4 |
Correct |
393 ms |
63304 KB |
Output is correct |
5 |
Correct |
438 ms |
67056 KB |
Output is correct |
6 |
Correct |
437 ms |
66908 KB |
Output is correct |
7 |
Correct |
442 ms |
67652 KB |
Output is correct |
8 |
Correct |
439 ms |
67332 KB |
Output is correct |
9 |
Correct |
441 ms |
67096 KB |
Output is correct |
10 |
Correct |
434 ms |
66920 KB |
Output is correct |
11 |
Correct |
230 ms |
62920 KB |
Output is correct |
12 |
Correct |
411 ms |
66940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
442 ms |
65372 KB |
Output is correct |
2 |
Correct |
431 ms |
65672 KB |
Output is correct |
3 |
Correct |
448 ms |
65152 KB |
Output is correct |
4 |
Correct |
445 ms |
65580 KB |
Output is correct |
5 |
Correct |
448 ms |
66348 KB |
Output is correct |
6 |
Correct |
491 ms |
68596 KB |
Output is correct |
7 |
Correct |
546 ms |
69580 KB |
Output is correct |
8 |
Correct |
625 ms |
65824 KB |
Output is correct |
9 |
Correct |
446 ms |
66320 KB |
Output is correct |
10 |
Correct |
433 ms |
65388 KB |
Output is correct |
11 |
Correct |
244 ms |
63472 KB |
Output is correct |
12 |
Correct |
514 ms |
69240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
49052 KB |
Output is correct |
2 |
Correct |
47 ms |
47352 KB |
Output is correct |
3 |
Correct |
46 ms |
47356 KB |
Output is correct |
4 |
Correct |
67 ms |
50680 KB |
Output is correct |
5 |
Correct |
56 ms |
48988 KB |
Output is correct |
6 |
Correct |
47 ms |
47480 KB |
Output is correct |
7 |
Correct |
47 ms |
47480 KB |
Output is correct |
8 |
Correct |
48 ms |
47580 KB |
Output is correct |
9 |
Correct |
47 ms |
47480 KB |
Output is correct |
10 |
Correct |
56 ms |
49144 KB |
Output is correct |
11 |
Correct |
47 ms |
47452 KB |
Output is correct |
12 |
Correct |
46 ms |
47356 KB |
Output is correct |
13 |
Correct |
46 ms |
47452 KB |
Output is correct |
14 |
Correct |
46 ms |
47480 KB |
Output is correct |
15 |
Correct |
46 ms |
47352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
390 ms |
63212 KB |
Output is correct |
2 |
Correct |
427 ms |
63360 KB |
Output is correct |
3 |
Correct |
563 ms |
69356 KB |
Output is correct |
4 |
Correct |
393 ms |
63304 KB |
Output is correct |
5 |
Correct |
438 ms |
67056 KB |
Output is correct |
6 |
Correct |
437 ms |
66908 KB |
Output is correct |
7 |
Correct |
442 ms |
67652 KB |
Output is correct |
8 |
Correct |
439 ms |
67332 KB |
Output is correct |
9 |
Correct |
441 ms |
67096 KB |
Output is correct |
10 |
Correct |
434 ms |
66920 KB |
Output is correct |
11 |
Correct |
230 ms |
62920 KB |
Output is correct |
12 |
Correct |
411 ms |
66940 KB |
Output is correct |
13 |
Correct |
442 ms |
65372 KB |
Output is correct |
14 |
Correct |
431 ms |
65672 KB |
Output is correct |
15 |
Correct |
448 ms |
65152 KB |
Output is correct |
16 |
Correct |
445 ms |
65580 KB |
Output is correct |
17 |
Correct |
448 ms |
66348 KB |
Output is correct |
18 |
Correct |
491 ms |
68596 KB |
Output is correct |
19 |
Correct |
546 ms |
69580 KB |
Output is correct |
20 |
Correct |
625 ms |
65824 KB |
Output is correct |
21 |
Correct |
446 ms |
66320 KB |
Output is correct |
22 |
Correct |
433 ms |
65388 KB |
Output is correct |
23 |
Correct |
244 ms |
63472 KB |
Output is correct |
24 |
Correct |
514 ms |
69240 KB |
Output is correct |
25 |
Correct |
57 ms |
49052 KB |
Output is correct |
26 |
Correct |
47 ms |
47352 KB |
Output is correct |
27 |
Correct |
46 ms |
47356 KB |
Output is correct |
28 |
Correct |
67 ms |
50680 KB |
Output is correct |
29 |
Correct |
56 ms |
48988 KB |
Output is correct |
30 |
Correct |
47 ms |
47480 KB |
Output is correct |
31 |
Correct |
47 ms |
47480 KB |
Output is correct |
32 |
Correct |
48 ms |
47580 KB |
Output is correct |
33 |
Correct |
47 ms |
47480 KB |
Output is correct |
34 |
Correct |
56 ms |
49144 KB |
Output is correct |
35 |
Correct |
47 ms |
47452 KB |
Output is correct |
36 |
Correct |
46 ms |
47356 KB |
Output is correct |
37 |
Correct |
46 ms |
47452 KB |
Output is correct |
38 |
Correct |
46 ms |
47480 KB |
Output is correct |
39 |
Correct |
46 ms |
47352 KB |
Output is correct |
40 |
Correct |
368 ms |
66788 KB |
Output is correct |
41 |
Correct |
390 ms |
67064 KB |
Output is correct |
42 |
Correct |
386 ms |
67060 KB |
Output is correct |
43 |
Correct |
238 ms |
65400 KB |
Output is correct |
44 |
Correct |
265 ms |
65596 KB |
Output is correct |
45 |
Correct |
487 ms |
68200 KB |
Output is correct |
46 |
Correct |
460 ms |
68092 KB |
Output is correct |
47 |
Correct |
390 ms |
66788 KB |
Output is correct |
48 |
Correct |
245 ms |
62456 KB |
Output is correct |
49 |
Correct |
338 ms |
66428 KB |
Output is correct |
50 |
Correct |
429 ms |
67720 KB |
Output is correct |
51 |
Correct |
449 ms |
68328 KB |
Output is correct |