This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define LL long long
#define F first
#define S second
#define mp make_pair
using namespace std;
void load() {
#ifndef ONLINE_JUDGE
freopen(".inp","r",stdin);
freopen(".out","w",stdout);
#endif // ONLINE_JUDGE
}
int n,m,a,b,c,d;
const int N = 1e5 + 123;
typedef pair < LL , int > II;
vector < II > ed[N];
typedef pair < LL , II > IIII;
LL dp[3][N],f[N][4],ans ;
void dij(int s, int cs) {
for (int i = 1 ; i <= n ; ++ i)
dp[cs][i] = 1e18;
dp[cs][s] = 0;
priority_queue < II , vector < II > , greater < II > > q;
q.push(mp(0,s));
while (!q.empty()) {
II b = q.top();
q.pop();
if (b.F > dp[cs][b.S]) continue;
for (II tmp : ed[b.S]) {
int v = tmp.F, w = tmp.S;
if (dp[cs][v] > b.F + w)
dp[cs][v] = b.F + w,
q.push(mp(dp[cs][v],v));
}
}
}
void dij_2(int s) {
for (int i = 1 ; i <= n ; ++ i)
for (int j = 0 ; j < 4 ; ++ j)
f[i][j] = 1e18;
f[s][0] = 0;
if (dp[1][s] + dp[2][s] == dp[2][a])
f[s][1] = 0;
priority_queue < IIII , vector <IIII>, greater < IIII > > q;
q.push(mp(f[s][0],mp(s,0)));
q.push(mp(f[s][1],mp(s,1)));
while (!q.empty()) {
IIII b = q.top();
q.pop();
if (f[b.S.F][b.S.S] < b.F) continue;
for (II tmp : ed[b.S.F]) {
int v = tmp.F, w = tmp.S, typ = b.S.S;
if (typ == 0) {
if (f[v][0] > b.F + w)
f[v][0] = b.F + w,
q.push(mp(f[v][0], mp(v,0)));
if (dp[1][v] + dp[2][v] == dp[2][a] && f[v][1] > b.F + w)
f[v][1] = b.F + w,
q.push(mp(f[v][1], mp(v,1)));
}
if (typ == 1) {
if (f[v][0] > b.F + w)
f[v][0] = b.F + w,
q.push(mp(f[v][0], mp(v,0)));
int u = b.S.F;
if (dp[1][u] + dp[2][v] + w == dp[2][a] && f[v][2] > b.F)
f[v][2] = b.F,
q.push(mp(f[v][2],mp(v,2)));
}
if (typ == 2) {
if (f[v][3] > b.F + w)
f[v][3] = b.F + w,
q.push(mp(f[v][3], mp(v,3)));
int u = b.S.F;
if (dp[1][u] + dp[2][v] + w == dp[2][a] && f[v][2] > b.F)
f[v][2] = b.F,
q.push(mp(f[v][2],mp(v,2)));
}
if (typ == 3) {
if (f[v][3] > b.F + w)
f[v][3] = b.F + w,
q.push(mp(f[v][3], mp(v,3)));
}
}
}
ans = min(ans,min(f[d][0],f[d][1]));
ans = min(ans,min(f[d][2],f[d][3]));
return ;
}
void trungtt() {
scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d);
for (int i = 1 ; i <= m ; ++ i) {
int u,v,val;
scanf("%d%d%d",&u,&v,&val);
ed[u].push_back(mp(v,val));
ed[v].push_back(mp(u,val));
}
ans = 1e18;
dij(a,1);
dij(b,2);
dij_2(c);
swap(a,b);
dij(a,1);
dij(b,2);
dij_2(c);
printf("%lld",ans);
}
int main() {
//load();
trungtt();
return 0;
}
Compilation message (stderr)
commuter_pass.cpp: In function 'void load()':
commuter_pass.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(".inp","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(".out","w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void trungtt()':
commuter_pass.cpp:106: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,&a,&b,&c,&d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&u,&v,&val);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |