P2934 [USACO09JAN]Safe Travel G 题解

· · 题解

P2934 [USACO09JAN] Safe Travel G

更好体验
题目

考点：最短路树 & 并查集缩点

正式开始讲解

题意：求在不经过原来 1 节点到 i 节点最短路上最后一条边的前提下，1 节点到 i 节点的最短路。

样例的图画出来是这样：

既然最短路唯一，我们可以记录 1 节点到每个节点的最短路的最后一条边的起点，也就是最后一个松弛它的节点，作为它的父亲，构造出一棵根为 1 号节点的最短路树。因为最短路唯一，最短路树也是唯一的。

由样例构造出的最短路树是这样的：

红色边为最短路树上的边，黑色边不属于最短路树，我们将不属于最短路树的边称为非树边。为了方便，我们把树边标记为红色，非树边为黑色。

题目求的路径，也就是在不经过最短路树上 i 节点到它父亲的边的前提下，1 节点到 i 节点的最短路，为方便，我们将其称为最好路径。

很显然，如果每次都断开边重构最短路树的话，本质上就是跑了 n 遍最短路，时间复杂度 O(n^2\log n)。

根据最短路树的性质，在断开 i 节点到它父亲的边后，最短路一定会经过至少一条非树边，而且仅经过一条非树边，因为如果该路径经过多条非树边，那么总有一条非树边可以用最短路树上的一条不包含被断开边的链替代。

因此，断开边后，1 节点到 i 节点的满足要求的最短路一定是 树上路径-->非树边-->树上路径 的形式。

我们做如下定义：

那么我们不妨换一个角度，枚举每一条非树边，考虑有哪些节点到源点的“最好路径”可能经过这条边。经过一些考虑，我们发现，对于边 (u,v)，一个节点 i 到 1 的最好路径可能经过它，当且仅当 i 是 L(u,v) 的后代且是 u 或 v 的祖先。

因此，对于每个点 i，ans_i=\min\limits_{u,v}{(d_v+w_{u,v}+d_u-d_i)}

因为 d_i 不变，所以 d_v+w_{u,v}+d_u-d_i 取得最小值，当且仅当 d_v+w_{u,v}+d_u 取得最小值。

所以，如果将非树边 (u,v) 按 d_u+w_{u,v}+d_v 从小到大排序，再枚举这条边能更新的点，那么每个点第一次被更新时的 ans_i 就是最终答案。那么我们每次更新完就将这个点删除，正确性仍保证。用并查集缩点解决即可。

时间复杂度：O(n\log n+m\log m)

Code

删除上一条边后如果 1 号节点不能到达 i，输出 -1

翻译这道题的人漏了好多要素

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<ll,int> pr;

int n,m;
struct edge{
    int v;
    ll w;
    edge(){} edge(int v_,ll w_){ v=v_,w=w_; }
};
vector<edge> e[100005];

ll d[100005];
int fa[100005][30],dep[100005];

priority_queue<pr> q;
void dijkstra(){
    while(!q.empty()){ q.pop(); }
    for(int i=1;i<=n;i++){ d[i]=-1; }
    d[1]=0;q.push(make_pair(0,1));
    while(!q.empty()){
        pr nw=q.top();q.pop();
        int u=nw.second;
        for(int i=e[u].size()-1;i>=0;i--){
            int v=e[u][i].v;
            ll w=e[u][i].w;
            if(d[v]==-1 || d[v]>d[u]+w){
                d[v]=d[u]+w;
                fa[v][0]=u;
                dep[v]=dep[u]+1;
                q.push(make_pair(-d[v],v));
            }
        }
    }
}

void init(){
    for(int j=1;j<=25;j++){
        for(int i=1;i<=n;i++){
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
}
int lca(int u,int v){
    if(dep[v]>dep[u]){
        swap(u,v);
    }
    for(int i=25;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    for(int i=25;i>=0;i--) if(fa[u][i]!=fa[v][i]){ u=fa[u][i];v=fa[v][i]; }
    return fa[u][0];
}

struct nont{
    int u,v;
    ll w;
    nont(){} nont(int u_,int v_,ll w_){ u=u_,v=v_,w=w_; }
};
bool operator<(nont a,nont b){
    return d[a.u]+d[a.v]+a.w < d[b.u]+d[b.v]+b.w;
}

nont nt[200005];int tp=0;

ll ans[100005];

int nx[100005];
int getfa(int u){
    return (u==nx[u])?u:(nx[u]=getfa(nx[u]));
}

int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b;ll t;
        scanf("%d%d%lld",&a,&b,&t);
        e[a].push_back(edge(b,t));
        e[b].push_back(edge(a,t));
    }

    dijkstra();
    init();

    for(int i=1;i<=n;i++){
        ans[i]=-1;  // 没有满足条件路径一定要输出 -1 否则 100Pts -> 40Pts
        nx[i]=i;
        for(int j=e[i].size()-1;j>=0;j--){
            int u=i,v=e[i][j].v;
            ll w=e[i][j].w;
            if(fa[v][0]!=u && fa[u][0]!=v && u<v){
                nt[++tp]=nont(u,v,w);
            }
        }
    }
    sort(nt+1,nt+tp+1);

    for(int i=1;i<=tp;i++){
        int x=nt[i].u,y=nt[i].v;
        ll kw=d[x]+d[y]+nt[i].w;
        int u=getfa(x),v=getfa(y);
        while(u!=v){
            if(dep[u]<dep[v]){
                swap(u,v);
            }
            ans[u]=kw-d[u];
            nx[u]=fa[u][0];
            u=getfa(u);
        }
    }

    for(int i=2;i<=n;i++){
        printf("%lld\n",ans[i]);
    }

    return 0;

}