제출 #82479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82479		151104	Commuter Pass (JOI18_commuter_pass)	C++11	24 / 100	47 ms	2304 KiB

commuter_pass

#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]=1e15;
    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=f[C][D];
        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=f[C][D];
    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]);
    swap(A,B);
    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;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45