题意简化

给定一张n个点m条边的图,问从一号点到其他点的次短路长度

题解

先建出图的最短路树,然后把非树边排序,依次枚举更新,并查集判重即可

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define in inline
#define get getchar()
in int read()
{
    int t=0; char ch=get;
    while(ch<'0' || ch>'9') ch=get;
    while(ch<='9' && ch>='0') t=t*10+ch-'0', ch=get;
    return t;
}
const int _=4e5+5;
struct edge{
    int to,ne,w,fr;
}e[_],ft[_];//ft记录非树边
int vis[_],cnt,dis[_],father[_],from[_],tot,h[_],n,m,ans[_]; //from记录最短路树中父亲,cnt是非树边的数量
in void add(int x,int y,int z)
{
    e[++tot].ne=h[x],e[tot].fr=x,e[tot].w=z,e[tot].to=y,h[x]=tot;
}
in void dijkstra() //dijkstra
{
    priority_queue<pair<int ,int> >q;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(re int i=h[u];i;i=e[i].ne)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w)
            {
                from[v]=u;
                dis[v]=dis[u]+e[i].w;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
    return ;
}
in int cmp(edge x,edge y)
{
    return x.w<y.w;
}
in int find(int x)
{
    if(father[x]==x) return x;
    father[x]=find(father[x]);
    return father[x];
}
int main()
{
    n=read(),m=read();
    for(re int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    dijkstra();
    for(re int i=1;i<=m*2;i+=2) //找非树边
    {
        int u=e[i].fr,v=e[i].to;
        if(from[u]==v||from[v]==u) continue;
        ft[++cnt].to=v,ft[cnt].fr=u,ft[cnt].w=dis[u]+e[i].w+dis[v];
    }
    sort(ft+1,ft+1+cnt,cmp);
    for(re int i=1;i<=n;i++) father[i]=i;
    memset(ans,0,sizeof(ans));
    for(re int i=1;i<=cnt;i++) //枚举更新非树边求答案
    {
        int u=find(ft[i].fr),v=find(ft[i].to);
        while(u!=v)
        {
            if(dis[u]<dis[v]) swap(u,v);
            ans[u]=ft[i].w-dis[u];
            father[u]=from[u];
            u=find(u);
        }
    }
    for(re int i=2;i<=n;i++)cout<<(ans[i]==0?-1:ans[i])<<endl;
}

[USACO09JAN]安全出行Safe Travel

原文：https://www.cnblogs.com/yzhx/p/11649902.html