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 fort(i,a,b) for(ll i=(a);i<=(b);++i)
#define N 305
using namespace std;
ll n,m,A,B,C,D,f[N][N],u,v,w;
int main()
{
// freopen("t.inp","r",stdin);
//freopen("t.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
cin>>A>>B;
cin>>C>>D;
fort(i,1,n) fort(j,1,n) if (i!=j) f[i][j]=1e9;
fort(i,1,m){
cin>>u>>v>>w;
f[u][v]=min(f[u][v],w);
f[v][u]=min(f[v][u],w);
}
fort(k,1,n) fort(i,1,n) fort(j,1,n) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
if (A==C){
ll ans=1e9;
fort(x,1,n) if (f[A][x]+f[x][B]==f[A][B]) ans=min(ans,f[x][D]);
cout<<ans;
return 0;
}
ll ans=1e9;
fort(x,1,n) fort(y,1,n)
if (f[A][x]+f[x][y]+f[y][B]==f[A][B]) ans=min(ans,f[x][C]+f[y][D]);
cout<<ans;
return 0;
}
# | 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... |