Submission #1278724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278724		aryan	Relay Marathon (NOI20_relaymarathon)	C++17	0 / 100	564 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] --;
    }
    multiset<pair<int,int>> ms;

    for(int i = 0;i < k;i++){
        int e = s[i];
        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});
                }
            }
        }
        for(int j = 0;j < k;j++){
            int e2 = s[j];
            if(e == e2) continue;
            ms.insert({dist[e][e2],min(e,e2)});
        }
       }

    int ans = inf;

    for(int &s1 : s){
        for(int &e : s){
            if(e == s1) continue;
            ms.erase(ms.find({dist[s1][e],min(s1,e)}));
        }
        for(int &f1 : s){
            if(s1 == f1) continue;
            for(int &e : s){
                if(e == f1) continue;
                ms.erase(ms.find({dist[f1][e],min(e,f1)}));
            }
            if(!ms.empty()){
                 ans = min(ans,ms.begin()->first + dist[s1][f1]);
            }
            for(int &e : s){
                if(e == f1) continue;
                ms.insert({dist[f1][e],min(f1,e)});
            }
        }
        for(int &e : s){
            if(e == s1) continue;
            ms.insert({dist[s1][e],min(s1,e)});
        }
    }
    cout << ans << '\n';

    return 0;
}

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