Submission #1291315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291315		aryan	Relay Marathon (NOI20_relaymarathon)	C++20	0 / 100	6089 ms	329372 KiB

RelayMarathon

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

using i64 = long long;

struct Data{
    int u,src;
    i64 w;
    Data() {};
    Data(int _u,i64 _w,int _src){
        u = _u;
        w = _w;
        src = _src;
    }
    bool operator <(const Data b) const{
        return this->w > b.w;
    }
};
int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<pair<int,int>>> adj(n);
    vector<bool> sp(n);
    for(int i = 0;i < m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        u --;
        v --;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    for(int i = 0;i < k;i++){
        int x;
        cin >> x;
        x --;
        sp[x] = true;
    }
    const i64 inf = 1e18;
    vector<vector<pair<int,i64>>> best(n);
    int lm = 3; // no of k shortest paths
    for(int i = 0;i < n;i++){
        for(int j = 0;j < lm;j++){
            best[i].push_back({n,inf});
        }
    }

    function<int(int,int)> give = [&](int u,int src){
            int bad = -1;
            for(int i = 0;i < lm;i++){
            if(src == best[u][i].first){
                bad = -1;
                break;
            }
            if(bad == -1) bad = i;
            if(best[u][bad].second < best[u][i].second){
                bad = i;
            }
        }
        return bad;
    };

    priority_queue<Data> pq;
    for(int i = 0;i < n;i++){
        if(sp[i]){
            pq.push(Data(i,0,i));
        }
    }
    while(!pq.empty()){
        Data p = pq.top();
        pq.pop();
        int u = p.u;
        i64 w = p.w;
        int src = p.src;

        int bad = give(u,src);
        if(bad == -1) continue;
        else if(best[u][bad].second > w){
            best[u][bad] = {src,w};
        }else continue;

        for(pair<int,int> ed : adj[u]){
            int v = ed.first;
            int wi = ed.second;
            i64 d = w + wi;
            int bad2 = give(v,src);
            if(bad2 == -1) continue;
            if(best[v][bad2].second > d){
                // best[v][bad2] = {src,d};
                pq.push(Data(v,d,src));
            }
        }
    }
    // for(int i = 0;i < n;i++){
    //     cout << i << " : " << '\n';
    //     for(int j = 0;j < lm;j++){
    //         cout << best[i][j].first << " " << best[i][j].second << '\n';
    //     }
    //     cout << '\n';
    // }

    i64 ans = inf;
    for(int i = 2;i < n;i++){
        for(int j = 0;j < lm;j++){
            if(best[i][j].first != i && sp[i]) ans = min(ans,best[i][j].second);
        }
    }
    cout << ans + 1 << '\n';

    return 0;
}

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