#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N=2e5+5;
int n,m,S,T,U,V;
long long D[N][4],dp[N],fix[N];
vector < pair < long long , int > > v[N];
void Dijkstra(int type) {
multiset < pair < long long , int > > st;
for (int i=1; i<=n; i++)
fix[i]=0,D[i][type]=1e17;
if (!type) D[V][0]=0,st.insert({D[V][0],V});
else
if (type==1) D[U][1]=0,st.insert({D[U][1],U});
else
if (type==2) D[S][2]=0,st.insert({D[S][3],S});
else
if (type==3) D[T][3]=0,st.insert({D[T][3],T});
while (st.size()) {
int x=(*st.begin()).S;
st.erase(st.find(*st.begin()));
if (fix[x]) continue;
fix[x]=1;
for (int i=0; i<v[x].size(); i++){
long long to=v[x][i].F,dist=v[x][i].S;
if (!fix[to] && D[x][type]+dist<D[to][type]) {
D[to][type]=D[x][type]+dist;
st.insert({D[to][type],to});
}
}
}
}
void FillDp(int type) {
multiset < pair < long long , int > > st;
long long d[N];
for (int i=1; i<=n; i++)
fix[i]=0,d[i]=1e17,dp[i]=1e17;
if (!type) {
d[T]=0,dp[T]=D[T][0];
st.insert({d[T],T});
}
else {
d[S]=0,dp[S]=D[S][0];
st.insert({d[S],S});
}
while (st.size()) {
int x=(*st.begin()).S;
st.erase(st.find(*st.begin()));
if (fix[x]) continue;
fix[x]=1;
for (int i=0; i<v[x].size(); i++) {
long long to=v[x][i].F,dist=v[x][i].S;
if (!fix[to] && d[x]+dist<d[to] && D[to][2]+D[to][3]==D[S][3]) {
dp[to]=min(dp[x],D[to][0]);
d[to]=d[x]+dist;
st.insert({d[to],to});
}
}
}
}
main () {
ios::sync_with_stdio(false);
cin>>n>>m;
cin>>S>>T;
cin>>U>>V;
for (int i=1; i<=m; i++) {
int a,b,c;
cin>>a>>b>>c;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
Dijkstra(0);
Dijkstra(1);
Dijkstra(2);
Dijkstra(3);
FillDp(0);
long long ANS=D[V][1];
for (int x=1; x<=n; x++)
ANS=min(ANS,dp[x]+D[x][1]);
FillDp(1);
for (int x=1; x<=n; x++)
ANS=min(ANS,dp[x]+D[x][1]);
cout<<ANS<<endl;
}
Compilation message
commuter_pass.cpp: In function 'void Dijkstra(int)':
commuter_pass.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[x].size(); i++){
~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void FillDp(int)':
commuter_pass.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[x].size(); i++) {
~^~~~~~~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:76:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
537 ms |
24936 KB |
Output is correct |
2 |
Correct |
510 ms |
24312 KB |
Output is correct |
3 |
Correct |
578 ms |
24948 KB |
Output is correct |
4 |
Correct |
575 ms |
24944 KB |
Output is correct |
5 |
Correct |
513 ms |
23840 KB |
Output is correct |
6 |
Correct |
572 ms |
25336 KB |
Output is correct |
7 |
Incorrect |
499 ms |
24312 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
571 ms |
24636 KB |
Output is correct |
2 |
Correct |
583 ms |
24056 KB |
Output is correct |
3 |
Correct |
532 ms |
24056 KB |
Output is correct |
4 |
Correct |
548 ms |
24064 KB |
Output is correct |
5 |
Correct |
582 ms |
24184 KB |
Output is correct |
6 |
Correct |
551 ms |
24440 KB |
Output is correct |
7 |
Correct |
603 ms |
24056 KB |
Output is correct |
8 |
Correct |
580 ms |
24312 KB |
Output is correct |
9 |
Correct |
556 ms |
24056 KB |
Output is correct |
10 |
Correct |
597 ms |
24128 KB |
Output is correct |
11 |
Correct |
337 ms |
15836 KB |
Output is correct |
12 |
Correct |
625 ms |
24824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
6392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
537 ms |
24936 KB |
Output is correct |
2 |
Correct |
510 ms |
24312 KB |
Output is correct |
3 |
Correct |
578 ms |
24948 KB |
Output is correct |
4 |
Correct |
575 ms |
24944 KB |
Output is correct |
5 |
Correct |
513 ms |
23840 KB |
Output is correct |
6 |
Correct |
572 ms |
25336 KB |
Output is correct |
7 |
Incorrect |
499 ms |
24312 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |