#include <bits/stdc++.h>
using namespace std;
#define INF (1LL<<60)
typedef long long ll;
typedef pair <int,int> pii;
int N,M,S,T,U,V,deg[101010];
ll du[101010],dv[101010],d[101010],disu[101010],disv[101010],dist[101010];
vector <pii> adj[101010];
vector <int> dag[101010];
struct Data{
int u,v ; ll w ;
bool operator<(const Data &r)const{
return w>r.w;
}
};
priority_queue <Data> pq;
queue <int> q;
int main(){
scanf("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
for(int i=1;i<=M;i++)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
adj[u].push_back(pii(v,w));
adj[v].push_back(pii(u,w));
}
for(int i=1;i<=N;i++) dist[i] = INF;
pq.push(Data{0,S,0});
while(!pq.empty()){
Data t = pq.top(); pq.pop();
if(t.w<=dist[t.v]) deg[t.v]++, dag[t.u].push_back(t.v);
if(t.w>=dist[t.v]) continue;
dist[t.v] = t.w;
for(pii nx: adj[t.v]) pq.push((Data){t.v,nx.first,nx.second+t.w});
}
for(int i=1;i<=N;i++) disu[i] = INF;
pq.push(Data{0,U,0});
while(!pq.empty()){
Data t = pq.top();
pq.pop();
if (t.w >= disu[t.v]) continue;
disu[t.v] = t.w;
for (pii nx : adj[t.v]) pq.push((Data){t.v, nx.first, nx.second+t.w});
}
for(int i=1;i<=N;i++) disv[i] = INF;
pq.push(Data{0,V,0});
while(!pq.empty()){
Data t = pq.top();
pq.pop();
if(t.w>=disv[t.v]) continue;
disv[t.v] = t.w;
for(pii nx:adj[t.v]) pq.push((Data){t.v,nx.first,nx.second+t.w});
}
q.push(S);
for(int i=1;i<=N;i++) du[i] = disu[i],dv[i] = disv[i],d[i] = INF;
while(!q.empty()){
int u = q.front(); q.pop();
d[u] = min(d[u],du[u]+disv[u]);
d[u] = min(d[u],dv[u]+disu[u]);
for(int v:dag[u]){
d[v] = min(d[v],d[u]);
du[v] = min(du[v],du[u]);
dv[v] = min(dv[v],dv[u]);
deg[v]--; if(deg[v]==0) q.push(v);
}
}
printf("%lld\n",min(d[T],disu[V]));
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&u,&v,&w);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
659 ms |
20444 KB |
Output is correct |
2 |
Correct |
558 ms |
24156 KB |
Output is correct |
3 |
Correct |
571 ms |
24712 KB |
Output is correct |
4 |
Correct |
671 ms |
24096 KB |
Output is correct |
5 |
Correct |
638 ms |
24292 KB |
Output is correct |
6 |
Correct |
698 ms |
24264 KB |
Output is correct |
7 |
Correct |
585 ms |
25148 KB |
Output is correct |
8 |
Correct |
568 ms |
25104 KB |
Output is correct |
9 |
Correct |
703 ms |
25084 KB |
Output is correct |
10 |
Correct |
445 ms |
24868 KB |
Output is correct |
11 |
Correct |
195 ms |
18424 KB |
Output is correct |
12 |
Correct |
638 ms |
25684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
712 ms |
20532 KB |
Output is correct |
2 |
Correct |
544 ms |
20548 KB |
Output is correct |
3 |
Correct |
534 ms |
24020 KB |
Output is correct |
4 |
Correct |
536 ms |
23780 KB |
Output is correct |
5 |
Correct |
535 ms |
23800 KB |
Output is correct |
6 |
Correct |
552 ms |
24808 KB |
Output is correct |
7 |
Correct |
544 ms |
24528 KB |
Output is correct |
8 |
Correct |
564 ms |
23556 KB |
Output is correct |
9 |
Correct |
548 ms |
24068 KB |
Output is correct |
10 |
Correct |
566 ms |
23524 KB |
Output is correct |
11 |
Correct |
207 ms |
18608 KB |
Output is correct |
12 |
Correct |
551 ms |
24708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
6388 KB |
Output is correct |
2 |
Correct |
8 ms |
5112 KB |
Output is correct |
3 |
Correct |
7 ms |
5112 KB |
Output is correct |
4 |
Correct |
68 ms |
8316 KB |
Output is correct |
5 |
Correct |
41 ms |
7232 KB |
Output is correct |
6 |
Correct |
8 ms |
5240 KB |
Output is correct |
7 |
Correct |
9 ms |
5368 KB |
Output is correct |
8 |
Correct |
10 ms |
5368 KB |
Output is correct |
9 |
Correct |
8 ms |
5240 KB |
Output is correct |
10 |
Correct |
34 ms |
7408 KB |
Output is correct |
11 |
Correct |
6 ms |
5112 KB |
Output is correct |
12 |
Correct |
7 ms |
5112 KB |
Output is correct |
13 |
Correct |
7 ms |
5112 KB |
Output is correct |
14 |
Correct |
7 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
5240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
659 ms |
20444 KB |
Output is correct |
2 |
Correct |
558 ms |
24156 KB |
Output is correct |
3 |
Correct |
571 ms |
24712 KB |
Output is correct |
4 |
Correct |
671 ms |
24096 KB |
Output is correct |
5 |
Correct |
638 ms |
24292 KB |
Output is correct |
6 |
Correct |
698 ms |
24264 KB |
Output is correct |
7 |
Correct |
585 ms |
25148 KB |
Output is correct |
8 |
Correct |
568 ms |
25104 KB |
Output is correct |
9 |
Correct |
703 ms |
25084 KB |
Output is correct |
10 |
Correct |
445 ms |
24868 KB |
Output is correct |
11 |
Correct |
195 ms |
18424 KB |
Output is correct |
12 |
Correct |
638 ms |
25684 KB |
Output is correct |
13 |
Correct |
712 ms |
20532 KB |
Output is correct |
14 |
Correct |
544 ms |
20548 KB |
Output is correct |
15 |
Correct |
534 ms |
24020 KB |
Output is correct |
16 |
Correct |
536 ms |
23780 KB |
Output is correct |
17 |
Correct |
535 ms |
23800 KB |
Output is correct |
18 |
Correct |
552 ms |
24808 KB |
Output is correct |
19 |
Correct |
544 ms |
24528 KB |
Output is correct |
20 |
Correct |
564 ms |
23556 KB |
Output is correct |
21 |
Correct |
548 ms |
24068 KB |
Output is correct |
22 |
Correct |
566 ms |
23524 KB |
Output is correct |
23 |
Correct |
207 ms |
18608 KB |
Output is correct |
24 |
Correct |
551 ms |
24708 KB |
Output is correct |
25 |
Correct |
38 ms |
6388 KB |
Output is correct |
26 |
Correct |
8 ms |
5112 KB |
Output is correct |
27 |
Correct |
7 ms |
5112 KB |
Output is correct |
28 |
Correct |
68 ms |
8316 KB |
Output is correct |
29 |
Correct |
41 ms |
7232 KB |
Output is correct |
30 |
Correct |
8 ms |
5240 KB |
Output is correct |
31 |
Correct |
9 ms |
5368 KB |
Output is correct |
32 |
Correct |
10 ms |
5368 KB |
Output is correct |
33 |
Correct |
8 ms |
5240 KB |
Output is correct |
34 |
Correct |
34 ms |
7408 KB |
Output is correct |
35 |
Correct |
6 ms |
5112 KB |
Output is correct |
36 |
Correct |
7 ms |
5112 KB |
Output is correct |
37 |
Correct |
7 ms |
5112 KB |
Output is correct |
38 |
Correct |
7 ms |
5112 KB |
Output is correct |
39 |
Correct |
7 ms |
5240 KB |
Output is correct |
40 |
Correct |
641 ms |
24064 KB |
Output is correct |
41 |
Correct |
663 ms |
24424 KB |
Output is correct |
42 |
Correct |
685 ms |
24552 KB |
Output is correct |
43 |
Correct |
242 ms |
18564 KB |
Output is correct |
44 |
Correct |
183 ms |
18660 KB |
Output is correct |
45 |
Correct |
559 ms |
23848 KB |
Output is correct |
46 |
Correct |
549 ms |
23500 KB |
Output is correct |
47 |
Correct |
633 ms |
24032 KB |
Output is correct |
48 |
Correct |
208 ms |
18168 KB |
Output is correct |
49 |
Correct |
636 ms |
24068 KB |
Output is correct |
50 |
Correct |
579 ms |
23476 KB |
Output is correct |
51 |
Correct |
571 ms |
23640 KB |
Output is correct |