P2934题解

2023-08-16
作者没进水的脑子
~3.48K 字

1. P2934 [USACO09JAN]Safe Travel G
1. 1.1. 读题

P2934 [USACO09JAN]Safe Travel G

原题链接

读题

1.不成熟的想法
想必大家看完题之后都跟我一样有一个共同的想法，那就是跑次短路，但是稍微思考一下就会发现其实不然，下面举个反例：
我们看从1到6的最短路，应该是 1 -> 4 -> 6 ,如果跑次短路的话则会找到1 -> 2 -> 4 -> 6。诶，这不对吧，题目要求我们不经过1节点到i节点的最后一条边，也就是删去最短路上i节点的父边，但是这里并没有删，因此 次短路X。

2.真正的解题思路

这里介绍一种算法，最短路树。
最短路树顾名思义就是在确定最短路径后将此路构建为一棵树。这棵树的性质就是每个父节点到儿子节点的距离为最短路（废话）。当原图的一条边不在树上时，我们将其称为非树边。根据最短路树的性质，在断开i节点到它父亲的边后，最短路一定会经过至少一条非树边，而且仅经过一条非树边，因为如果该路径经过多条非树边，那么总有一条非树边可以用最短路树上的一条不包含被断开边的链替代。所以，断开i节点的父边后，其最短路径一定是树边 -> 非树边 -> 树边 的形式。下面直接贺别人的例子方便大家理解
接着，我们想想如何找到这条非树边。稍微想一下我们就能发现，只有边的两个节点的LCA的后代为i且i为两个节点其中一个节点的祖先时，这条边才有可能是最好路径。继续贺别人的例子

最后，节点i的答案长度

。因为

不变，所以当

最小时，答案最小。
所以我们将

按照

的大小来排序，再枚举这条边能更新的点，那么每个点第一次被更新时的

即为所求，每次更新完答案，我们就将这个点删去，以加快搜索进度。
复杂度:

。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010;
int n, m;
vector<pair<int, int>> g[N];
void file()
{
#ifndef ONLINE_JUDGE
    freopen("/workspaces/Code/test/test.in", "r", stdin);
    freopen("/workspaces/Code/test/test.out", "w", stdout);
#endif
}
struct node
{
    int name, dis;
    node(int name = 0, int dis = 0) : name(name), dis(dis) {}
    bool operator<(const node &a) const
    {
        return dis > a.dis;
    }
};
const int inf = 0x3f3f3f3f;
int dis[N];
int dep[N];
int f[N][27];
void dj()
{
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    dis[1] = 0;
    priority_queue<pair<int,int>> q;
    q.push(make_pair(0,1));
    while (q.size())
    {
        int u = q.top().second;
        q.pop();
        for (int i = 0; i < g[u].size(); i++)
        {
            int v = g[u][i].first;
            int w = g[u][i].second;
            if (dis[v] > dis[u] + w)
            {
                f[v][0]=u;
                dis[v] = dis[u] + w;
                dep[v]=dep[u]+1;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
}
void start() {
    for(int i=1;i<=25;i++) {
        for(int j=1;j<=n;j++) {
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
}
int ans[N];
struct Node{
    int u,v,val;
    Node(int u=0,int v=0,int val=0) :u(u),v(v),val(val) {}
}no[N];
int nxt[N];
int top=0;
bool operator <(Node a,Node b) {
    return dis[a.u]+dis[a.v] +a.val <dis[b.u]+dis[b.v]+b.val;
}
int check(int x) {
    return (x==nxt[x])?x:(nxt[x]=check(nxt[x]));
}
signed main()
{
    file();
    scanf("%lld%lld",&n,&m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, val;
        scanf("%lld%lld%lld",&u,&v,&val);
        g[u].push_back({v, val});
        g[v].push_back({u, val});
    }
    dj();
    start();
    for(int i=1;i<=n;i++) {
        ans[i]=-1;
        nxt[i]=i;
        for(int j=0;j<g[i].size();j++) {
            int u=i;
            int v=g[i][j].first;
            int w=g[i][j].second;
            if(f[v][0]==u||f[u][0]==v||u>=v) continue;
            no[++top]=Node(u,v,w);
        }
    }
    sort(no+1,no+top+1);
    for(int i=1;i<=top;i++) {
        int u=no[i].u;
        int v=no[i].v;
        int val=no[i].val+dis[u]+dis[v];
        int uf=check(u), vf=check(v);
        while(uf!=vf){
            if(dep[uf]<dep[vf]) swap(uf,vf);
            ans[uf]=val-dis[uf];
            nxt[uf]=f[uf][0];
            uf=check(uf);
        }
    }
    for(int i=2;i<=n;i++){
        printf("%lld\n",ans[i]);
    }
}

没进水的脑子

P2934 [USACO09JAN]Safe Travel G

读题