Submission #1278747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278747		aryan	Relay Marathon (NOI20_relaymarathon)	C++20	0 / 100	6100 ms	276428 KiB

RelayMarathon

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

using i64 = long long;

struct Data{
    int u,tot,src;
    Data(){};
    Data(int _u,int _tot,int _src){
        u = _u;
        tot = _tot;
        src = _src;
    }
    bool operator <(const Data &b) const{
       return b.tot > this->tot;
    }
};

struct comp{
    bool operator()(Data &a,Data &b) const{
        return b.tot < a.tot;
    }  
};

int main(){

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

    const int inf = 1e9 + 5;

    int n,m,k;
    cin >> n >> m >> k;
    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<multiset<pair<int,int>>> dist(n);
    priority_queue<Data,vector<Data>,comp> pq;

    int lm = 4;    
    for(int i = 0;i < n;i++){
        for(int j = 0;j < lm;j++){
            dist[i].insert({inf,-1});
        }
    }

    vector<int> s(k);
    for(int i = 0;i < k;i++){
        cin >> s[i];
        s[i] --;
        pq.push(Data(s[i],0,s[i]));
    }
    
    while(!pq.empty()){
        Data d = pq.top();
        pq.pop();
        int u = d.u;
        int tot = d.tot;
        int src = d.src;
        if(prev(dist[u].end())->first < tot) continue;
        bool ok = true;
        for(auto &p : dist[u]){
            if(p.second == src){
                ok = false;
                assert(p.first <= tot);
                break;
            }
        }        
        if(!ok) continue;
        dist[u].erase(prev(dist[u].end()));
        dist[u].insert({tot,src});

        for(auto &p : adj[u]){
            int v = p.first;
            int w = p.second;
            if(prev(dist[v].end())->first > tot + w){
                pq.push(Data(v,tot + w,src));
            }
        }
    }

    multiset<int> ms;
    for(int i = 0;i < k;i++){
        for(auto &p : dist[s[i]]){
            if(p.second != s[i]) ms.insert(p.first);
        }
    }

    // for(int e : ms){
    //     cout << e << '\n';
    // }

    int ans = inf;
    for(int i = 0;i < k;i++){
        int e = s[i];
        // taking e removin all
        for(auto &p : dist[e]){
            if(p.second == e) continue;
            // cerr << "erasing " << p.first << '\n';
            ms.erase(ms.find(p.first));
        }

        for(auto &p : dist[e]){
            int e2 = p.second;
            if(e2 == e || e2 == -1) continue;
            // taking e2
            for(auto &p2 : dist[e2]){
                if(p2.second == e2) continue;
                // cerr << "erasing " << p2.first << '\n';
                ms.erase(ms.find(p2.first));
            }
            if(!ms.empty()) ans = min(ans,*ms.begin() + p.first);
            for(auto &p2 : dist[e2]){
                if(p2.second == e2) continue;
                // cerr << "inserting " << p2.first << '\n';
                ms.insert(p2.first);
            }
        }
         for(auto &p : dist[e]){
            if(p.second == e) continue;
            // cerr << "inserting " << p.first << '\n';
            ms.insert(p.first);
        }
    }    

    cout << ans << '\n';

    return 0;
}

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