Submission #1278733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278733		aryan	Relay Marathon (NOI20_relaymarathon)	C++17	0 / 100	6098 ms	276388 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(){

    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] --;
        if(s[i] == 0 || s[i] == 1) continue;
        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));
            }
        }
    }

    int ans = inf;
    for(int i = 0;i < k;i++){
       ans = min(ans,next(dist[s[i]].begin())->first);
    }
    cout << ans + 1 << '\n';

    return 0;
}

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