Submission #1291333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291333		aryan	Relay Marathon (NOI20_relaymarathon)	C++20	17 / 100	6101 ms	336008 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;
    }
};

struct Data2{
    int u,v;
    i64 w;
    Data2() {};
    Data2(int _u,i64 _w,int _v){
        u = _u;
        w = _w;
        v = _v;
    }
    bool operator <(const Data2 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 = 5; // no of k shortest paths
    for(int i = 0;i < n;i++){
        for(int j = 0;j < lm;j++){
            best[i].push_back({-1,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';
    // }

    // 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);
    //     }
    // }
    multiset<Data2> ms;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < lm;j++){
            if(sp[i] && best[i][j].first != i){
                ms.insert(Data2(i,best[i][j].second,best[i][j].first));
                // cout << i << " " << best[i][j].second << " " << best[i][j].first << '\n';
             }
            }
    }
    i64 ans = inf;
    for(int i = 0;i < n;i++){
        if(!sp[i]) continue;
        for(pair<int,i64> p: best[i]){
            int v = p.first;
            i64 w = p.second;
            if(v == -1 || v == i) continue;
            vector<Data2> buf;
            while(!ms.empty()){
                Data2 d = *ms.begin();
                if(d.u == i || d.u == v || d.v == i || d.v == v){
                    ms.erase(ms.begin());
                    // cout << "erasing " << d.u << " " << d.v << " " << d.w << '\n';
                    buf.push_back(d);
                }else break;
            }
            if(!ms.empty()){
                // cout << "hello " << ms.begin()->w <<'\n';
                ans = min(ans,w + ms.begin()->w);
            }
            for(Data2 d : buf){
                // cout << "inserting " << d.u << " " << d.v << " " << d.w << '\n';
                ms.insert(d);
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

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