BZOJ-1576: [Usaco2009 Jan]安全路经Travel

Description

注意是无向图。
发现问题等价于在单源最短路树上每个点找到一个不经过和父亲之间的那条边的最短路径。枚举非树边x->y,长度为w，那么非树边覆盖的环上的点z（除了两个点的lca）都会有一条不经过该边的路径，其长度为dis[x]+dis[y]+w-dis[z]。dis[z]是个定值，那么每个点只需要求出来dis[x]+dis[y]+w最小即可。那么枚举所有的非树边的值，从小到大排序，并查集维护没有被更新的点，直接更新即可。时间复杂度O(nlogn+mlogn)

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100100
using namespace std;
int n,m;
int head[N],to[N<<2],nxt[N<<2],date[N<<2],cnt=1;
inline void add(int x,int y,int z)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; date[cnt]=z;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; date[cnt]=z;
}
struct dij
{
    int v,dis;
};
bool operator < (dij x,dij y){return x.dis>y.dis;}
priority_queue<dij>he;
int dis[N],path[N];
inline void dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0; he.push((dij){1,0}); int x,y;
    while(!he.empty())
    {
        x=he.top().v,y=he.top().dis; he.pop();
        if(y>dis[x]) continue;
        for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]>y+date[i])
        {
            dis[to[i]]=y+date[i];
            path[to[i]]=i;
            he.push((dij){to[i],dis[to[i]]});
        }
    }
}
struct node
{
    int x,y,z;
}z[N<<1];
bool cmp(node x,node y){return x.z<y.z;}
int fa[N],deep[N],top,f[N][17],ans[N],Log[N];
void dfs(int x)
{
    for(int i=1;(1<<i)<=deep[x];++i) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=head[x];i;i=nxt[i]) if(path[to[i]]==i)
        deep[to[i]]=deep[x]+1,f[to[i]][0]=x,dfs(to[i]);
}
int get_lca(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    int tmp=deep[x]-deep[y];
    for(int i=0;i<=Log[tmp];++i) if(tmp&(1<<i)) x=f[x][i];
    if(x==y) return x;
    for(int i=Log[deep[y]];~i;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main()
{
    scanf("%d%d",&n,&m); int x,y,zz;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&zz);
        add(x,y,zz);
    }
    dijkstra(); dfs(1);
    for(int i=1;i<=n;++i)
    {
        for(int j=head[i];j;j=nxt[j]) if(path[to[j]]!=j&&path[i]!=(j^1)&&i<to[j])
            z[++top]=(node){i,to[j],dis[i]+dis[to[j]]+date[j]};
    }
    sort(z+1,z+top+1,cmp); int anc;
    fa[1]=1; for(int i=2;i<=n;++i) fa[i]=i,Log[i]=Log[i>>1]+1;
    for(int i=1;i<=top;++i)
    {
        anc=get_lca(z[i].x,z[i].y);
        for(int j=find(z[i].x);deep[j]>deep[anc];j=find(f[j][0]))
            fa[j]=f[j][0],ans[j]=z[i].z;
        for(int j=find(z[i].y);deep[j]>deep[anc];j=find(f[j][0]))
            fa[j]=f[j][0],ans[j]=z[i].z;
    }
    for(int i=2;i<=n;++i)
        printf("%d\n",ans[i]==0?-1:ans[i]-dis[i]);
    return 0;
}