이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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... |