제출 #1113822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113822		Aviansh	Relay Marathon (NOI20_relaymarathon)	C++17	17 / 100	874 ms	1048576 KiB

RelayMarathon

#include <bits/stdc++.h>

using namespace std;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,k;
    cin >> n >> m >> k;
    int dist[n][n];
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            dist[i][j]=1e9;
        }
        dist[i][i]=0;
    }
    for(int i = 0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        u--;v--;
        dist[u][v]=w;
        dist[v][u]=w;
    }
    for(int k = 0;k<n;k++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    int spec[k];
    for(int i = 0;i<k;i++){
        cin >> spec[i];
        spec[i]--;
    }
    vector<pair<int,int>>d[k];
    for(int i = 0;i<k;i++){
        for(int j = i+1;j<k;j++){
            d[i].push_back({dist[spec[i]][spec[j]],j});
        }
        sort(d[i].begin(),d[i].end());
    }
    int ans = 2e9;
    for(int i = 0;i<k;i++){
        for(int j = i+1;j<k;j++){
            for(int l = 0;l<k;l++){
                if(i==l||j==l){
                    continue;
                }
                for(pair<int,int>p : d[l]){
                    if(p.second==i||p.second==j)
                        continue;
                    ans=min(ans,dist[spec[i]][spec[j]]+p.first);
                    break;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58