题解 P5304 【[GXOI/GZOI2019]旅行者】

· · 题解

Dijkstra。

这道题目简直是弟弟级别的……

考虑每条边 (u,v,w) 的贡献，我们可以处理出城市中离 u 最近的距离为 dis_1，离 v 最近的距离为 dis_2，那么这条边的权值就是 dis_1+dis_2+w，然后找到最短的一条就行了。

同时，我们还要记录这个城市的编号，如果两个城市相同，那么相当于走了一个环回到其本身了，不能计入答案。

正反跑两边 Dijkstra，分别染色。染色也就是在跑 Dijkstra 的过程中记录离这个点最近的城市，具体可以见代码。

#include<bits/stdc++.h>
#define MAXN 100005
#define MAXM 500005
#define reg register
#define inl inline
#define ll long long
using namespace std;
int cnt,fst[MAXN],to[MAXM],nxt[MAXM],w[MAXM];
int n,m,k,col[2][MAXN],a[MAXN],fr[MAXM],tx[MAXM],ww[MAXM];
ll dis[2][MAXM];
struct Node
{
    int u;
    ll dis;
    bool operator < (const Node &x) const
    {
        return x.dis<dis;
    }
};
priority_queue <Node> q;
template <typename T> inl void Read(reg T &x)
{
    x=0;
    reg int fu=1;
    reg char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') fu=-1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch-48);
    x*=fu;
}
inl void AddEdge(reg int u,reg int v,reg int c)
{
    to[++cnt]=v;
    nxt[cnt]=fst[u];
    fst[u]=cnt;
    w[cnt]=c;
}
inl void Dijkstra(reg int id)
{
    memset(dis[id],60,sizeof(dis[id]));
    memset(col[id],0,sizeof(col[id]));
    for(reg int i=1;i<=k;i++)
    {
        dis[id][a[i]]=0;
        col[id][a[i]]=a[i];
        q.push((Node){a[i],0});
    }
    while(!q.empty())
    {
        reg Node now=q.top();
        q.pop();
        reg int u=now.u;
        reg ll d=now.dis;
        if(d!=dis[id][u]) continue;
        for(reg int i=fst[u];i;i=nxt[i])
        {
            reg int v=to[i];
            if(dis[id][v]>dis[id][u]+w[i])
            {
                dis[id][v]=dis[id][u]+w[i];
                col[id][v]=col[id][u];
                q.push((Node){v,dis[id][v]});
            }
        }
    }
}
int main()
{
    int Time;
    Read(Time);
    while(Time--)
    {
        cnt=0;
        memset(fst,0,sizeof(fst));
        Read(n);
        Read(m);
        Read(k);
        for(reg int i=1;i<=m;i++)
        {
            int x,y,z;
            Read(x);
            Read(y);
            Read(z);
            fr[i]=x;
            tx[i]=y;
            ww[i]=z;
            if(x^y) AddEdge(x,y,z);
        }
        for(reg int i=1;i<=k;i++) Read(a[i]);
        Dijkstra(0);
        cnt=0;
        memset(fst,0,sizeof(fst));
        for(reg int i=1;i<=m;i++) if(fr[i]^tx[i]) AddEdge(tx[i],fr[i],ww[i]);
        Dijkstra(1);
        reg ll ans=1e18;
        for(reg int i=1;i<=m;i++)
        {
            reg int u=fr[i],v=tx[i],c=ww[i];
            if(col[0][u] && col[1][v] && col[0][u]!=col[1][v]) ans=min(ans,dis[0][u]+dis[1][v]+c);
        }
        printf("%lld\n",ans);
    }
    return 0;
}