Submission #1179235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179235		12345678	Relay Marathon (NOI20_relaymarathon)	C++20	25 / 100	2165 ms	71508 KiB

RelayMarathon

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, inf=1e9;

int n, m, k, u, v, w, mn[nx], hd[nx];
vector<int> s, tmp;
vector<pair<int, int>> d[nx];

pair<int, pair<int, int>> solve(vector<int> &x)
{
    pair<int, pair<int, int>> res={inf, {0, 0}};
    vector<pair<int, int>> cur={{0, x.size()-1}};
    while (!cur.empty())
    {
        vector<pair<int, int>> nw;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int i=1; i<=n; i++) mn[i]=inf, hd[i]=i;
        for (auto [l, r]:cur)
        {
            int md=(l+r)/2;
            for (int i=l; i<=md; i++) mn[x[i]]=0, pq.push({0, x[i]});
            if (l!=md) nw.push_back({l, md});
            if (md+1!=r) nw.push_back({md+1, r});
        }
        while (!pq.empty())
        {
            auto [cw, u]=pq.top();
            pq.pop();
            if (mn[u]<cw) continue;
            for (auto [v, w]:d[u]) if (mn[v]>cw+w) mn[v]=cw+w, hd[v]=hd[u], pq.push({mn[v], v});
        }
        for (auto i:x) if (mn[i]!=0) res=min(res, {mn[i], {i, hd[i]}});
        cur=nw;
    }
    return res;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k;
    for (int i=1; i<=m; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    for (int i=1; i<=k; i++) cin>>u, s.push_back(u);
    for (auto u:s) if (u!=1&&u!=2) tmp.push_back(u); 
    cout<<1+solve(tmp).first;
}

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