Submission #1179255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179255		12345678	Relay Marathon (NOI20_relaymarathon)	C++20	100 / 100	3087 ms	83416 KiB

RelayMarathon

#include <bits/stdc++.h>

using namespace std;

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

int n, m, k, u, v, w, ans=inf, mn[nx], hd[nx];
vector<int> s, tmp;
vector<pair<int, int>> d[nx];
pair<int, int> mx1={inf, 0}, smx1={inf, 0}, mx2={inf, 0}, smx2={inf, 0};

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;
}

void dijkstra(int st)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i=1; i<=n; i++) mn[i]=inf;
    mn[st]=0;
    pq.push({0, st});
    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, pq.push({mn[v], v});
    }
}

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);
    auto [mndist, node]=solve(s);
    //cout<<"debug "<<node.first<<' '<<node.second<<'\n';
    for (auto u:s) if (u!=node.first&&u!=node.second) tmp.push_back(u);
    ans=mndist+solve(tmp).first;
    //cout<<"ans "<<ans<<'\n';
    dijkstra(node.first);
    for (auto u:s)
    {
        if (u==node.first||u==node.second||mn[u]==inf) continue;
        if (mn[u]<mx1.first) swap(mx1, smx1), mx1={mn[u], u};
        else if (mn[u]<smx1.first) smx1={mn[u], u};
    }
    //cout<<"mx1 "<<node.first<<' '<<mx1.first<<' '<<mx1.second<<'\n'; 
    dijkstra(node.second);
    for (auto u:s)
    {
        if (u==node.first||u==node.second||mn[u]==inf) continue;
        if (mn[u]<mx2.first) swap(mx2, smx2), mx2={mn[u], u};
        else if (mn[u]<smx2.first) smx2={mn[u], u};
    }
    //cout<<"mx2 "<<node.second<<' '<<mx2.first<<' '<<mx2.second<<'\n'; 
    if (mx1.second!=mx2.second) ans=min(ans, mx1.first+mx2.first);
    else ans=min({ans, mx1.first+smx2.first, smx1.first+mx2.first});
    cout<<ans;
}

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