题解：P11321 [NOISG 2020 Qualification] Relay Marathon

· · 题解

Solution

先考虑子任务 3 怎么做。首先路径 1\to 2 必选，只需要考虑剩下的关键点中选择哪两个。

对剩下的关键点跑多源最短路。由超级源点对关键点连边权为 0 的边，跑 dijkstra。于是我们就能得到每个点 u 离最近关键点的距离 dis_u，也能得到每个点的最近关键点 b_u，或者说，这个图被分成若干个块，每个块对应一个关键点，块内的点都距离这个关键点最近。

考虑最近的两个关键点之间的路径一定经过两个块的交界处，所以枚举边 i，满足 b_{u_i} \ne b_{v_i}，求 dis_{u_i}+dis_{v_i} 的最小值。

考虑两对点怎么做。易证答案中的四个点中，必然有两个是距离最近的（或者你可以理解为就是子任务 3 求得的点），所以我们有两种思路，一种是两个距离最近的关键点连一条边，剩下两个距离次近的再连一条边，这可以仿照子任务 3 求出；另一种是两个距离最近的关键点分别找一个关键点连边，找到两个关键点距离最近的两个点，简单枚举即可。

时间复杂度在 Dijkstra 和排序，为 O(n\log n)。

Code

#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 2e5+5,S = 2e5+4;
int n,m,k,a[N],dis[5][N],pre[N],u[3000005],v[3000005],w[3000005],x,y,mmin=999999999,book[N];
bool vis[5][N];
struct node
{
    int v,w;
};
vector<node>vec[N];
priority_queue<PII,vector<PII>,greater<PII>>q;
PII o[N],p[N];
void dijkstra(int u,int k)
{
    memset(dis[k],0x3f,sizeof dis[k]);
    q.push({0,u});
    dis[k][u] = 0;
    while (!q.empty())
    {
        PII now = q.top();
        q.pop();
        if (vis[k][now.second]) continue;
        vis[k][now.second] = 1;
        for (node i: vec[now.second])
        {
            if (dis[k][i.v] > dis[k][now.second]+i.w)
            {
                dis[k][i.v] = dis[k][now.second]+i.w;

                if (now.second == S) pre[i.v] = i.v;
                else pre[i.v] = pre[now.second];
                q.push({dis[k][i.v],i.v});
            }
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        vec[u[i]].push_back({v[i],w[i]});
        vec[v[i]].push_back({u[i],w[i]});
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> a[i];
        book[a[i]] = 1;
        vec[S].push_back({a[i],0});
    }
    dijkstra(S,0);
    for (int i = 1; i <= m; i++)
        if (pre[u[i]] != pre[v[i]] && dis[0][u[i]]+dis[0][v[i]]+w[i] < mmin)
            mmin = dis[0][u[i]]+dis[0][v[i]]+w[i],x = pre[u[i]],y = pre[v[i]];
//  cout << x << ' ' << y << ' ' << mmin << '\n';
    dijkstra(x,1);
    dijkstra(y,2);
    int ans = 999999999;
    int cnt1 = 0,cnt2 = 0;
    for (int i = 1; i <= n; i++)
        if (book[i]) o[++cnt1] = {dis[1][i],i};
    sort(o+1,o+cnt1+1);
    for (int i = 1; i <= n; i++)
        if (book[i]) p[++cnt2] = {dis[2][i],i};
    sort(p+1,p+cnt2+1);
    if (cnt1 >= 4)
    {
        if (o[3].second == p[3].second) ans = min(o[3].first+p[4].first,o[4].first+p[3].first);
        else ans = o[3].first+p[3].first;
    }
    for (int i = 0; i < vec[S].size(); i++)
        if (vec[S][i].v == x || vec[S][i].v == y) vec[S][i].w = 999999999;
    dijkstra(S,3);
    int min1 = 999999999;
    for (int i = 1; i <= m; i++)
        if (pre[u[i]] != pre[v[i]] && dis[3][u[i]]+dis[3][v[i]]+w[i] < min1)
            min1 = dis[3][u[i]]+dis[3][v[i]]+w[i];
    cout << min(ans,mmin+min1);
    return 0;
}