제출 #1167718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167718		edga1	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	127 ms	1132 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;

long long dist[305][305];

int main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    int n,m,s,t,u,v;
    cin>>n>>m>>s>>t>>u>>v;
    int a=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            dist[i][j]=-1;
        }
    }
    for(int i=0; i<m; i++){
        int a,b,c;
        cin>>a>>b>>c;
        dist[a][b]=c;
        dist[b][a]=c;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int z=1; z<=n; z++){
                if((dist[i][j]==-1 || dist[i][z]+dist[z][j]<dist[i][j]) && dist[i][z]!=-1 && dist[z][j]!=-1 ){
                    dist[i][j]=dist[i][z]+dist[z][j];
                }
            }
        }
    }
    long long r=-1;
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            if(dist[s][t]==dist[s][i]+dist[i][j]+dist[j][t] || dist[s][t]==dist[s][j]+dist[j][i]+dist[i][t]){
                long long dv=min(dist[v][i],dist[v][j]), du=min(dist[u][i],dist[u][j]);
                if(r==-1 || dv+du<r) r=dv+du;
            }
        }
    }
    cout<<r;
}

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