제출 #1278354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278354		aryan	Relay Marathon (NOI20_relaymarathon)	C++17	5 / 100	6088 ms	1114112 KiB

RelayMarathon

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


int main(){

    const int inf = 1e9 + 5;

    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<int>> dist(n + 1,vector<int>(n + 1,inf));
    vector<vector<pair<int,int>>> adj(n);
    for(int i = 0;i < m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        u --;
        v --;
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    vector<int> s(k);
    for(int i = 0;i < k;i++){
        cin >> s[i];
        s[i] --;
    }

    for(int &e : s){
        dist[e][e] = 0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        pq.push({0,e});
        while(!pq.empty()){
            auto p = pq.top();
            int u = p.second;
            int tot = p.first;
            pq.pop();
            if(tot > dist[e][u]) continue;
            for(auto pp : adj[u]){
                int v = pp.first;
                int w = pp.second;
                if(dist[e][v] > tot + w){
                    dist[e][v] = tot + w;
                    pq.push({dist[e][v],v});
                }
            }
        }
        // cout << e << '\n';
        // for(int i = 0;i < n;i++){
        //     cout << dist[e][i] << " ";
        // }
        // cout << '\n';
    }

    int ans = inf;

    for(int &s1 : s){
        for(int &f1 : s){
            for(int &s2 : s){
                for(int &f2 : s){
                    set<int> st;
                    st.insert(s1);
                    st.insert(s2);
                    st.insert(f1);
                    st.insert(f2);
                    if((int) st.size() != 4) continue;
                    ans = min(ans,dist[s1][f1] + dist[s2][f2]);
                }
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

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