洛谷 P2934 安全出行Safe Travel

· · 题解

传送~

Description

有一张n个点m条边的无向图，对于每个u(1<u \leq n)，求删去1到u的最短路的最后一条边后，从1到u的最短距离

Solution

首先建出最短路树。新的最短路肯定不能走它到父亲的边，那么必须要找一个或两个中介点，使得它与1连通。设当前点位i，其中一个中介点位u。如果i与u有一条边直接连接，则距离为dis_u+w_{u,i}；或者在i的子树中存在一点v与u有边相连，则距离为dis_u+w_{u,v}+dis_v-dis_i。将两种情况统一，若u与点v有边相连(v=i或v在i的子树内)，则新的距离为dis_u+w_{u,v}+dis_v-dis_i。由于dis_i确定，所以只要dis_u+w_{u,v}+dis_v最小即可。到这里与上面的题解都差不多，但是这里给出一种用堆的做法。

在dfs的过程中，把每个点可以得到的所有dis_u+w_{u,v}+dis_v存在一个堆里。具体做法是先把所有儿子的堆合并(要用左偏树)，再枚举出边把新的u及其值加入堆中，最后取堆顶时删掉不满足条件的(即两个点都在子树内)。

Code

#include <bits/stdc++.h>
#define mk make_pair
#define fst first
#define snd second
using namespace std;
const int maxn = 1e5;
const int maxm = 2e5;
const int maxt = 4e6; 
const int inf = 1e9;
typedef pair<int, int> pii;
int n, m, tot, cnt, head[maxn+10], dis[maxn+10], done[maxn+10], pd[maxm*2+10], dfn[maxn+10], size[maxn+10], ans[maxn+10], root[maxn+10];
struct edge {
    int to, nex, dis;
} edges[maxm*2+10];
struct node {
    int to, ls, rs, fa, dis, val;
} t[maxt+10];
void addedge(int u, int v, int w) {
    edges[++tot] = (edge){v, head[u], w}; head[u] = tot;
    edges[++tot] = (edge){u, head[v], w}; head[v] = tot;
}
int find(int x) {
    return x == t[x].fa ? x : t[x].fa = find(t[x].fa);
}
int merge(int x, int y) {
    if (!x || !y) return x+y;
    if (t[x].val > t[y].val) swap(x, y);
    t[x].rs = merge(t[x].rs, y);
    t[t[x].rs].fa = x;
    if (t[t[x].ls].dis < t[t[x].rs].dis) swap(t[x].ls, t[x].rs);
    t[x].dis = t[t[x].rs].dis+1;
    return x;
}
int remove(int x) {
    /*t[t[x].ls].fa = t[x].ls;
    t[t[x].rs].fa = t[x].rs;
    t[x].fa = merge(t[x].ls, t[x].rs);
    t[x].ls = t[x].rs = t[x].dis = 0;
    return t[x].fa;*/
    return merge(t[x].ls, t[x].rs);
}
void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push(mk(dis[1] = 0, 1));
    while (!q.empty()) {
        int x = q.top().snd; q.pop();
        if (done[x]) continue;
        done[x] = 1;
        for (int i = head[x]; i; i = edges[i].nex) {
            edge e = edges[i];
            if (dis[e.to] > dis[x]+e.dis)
                q.push(mk(dis[e.to] = dis[x]+e.dis, e.to));
        }
    }
}
int check(int u, int v) {
    return dfn[v] >= dfn[u] && dfn[v] < dfn[u]+size[u];
}
void dfs(int u, int fa) {
    dfn[u] = ++size[0]; size[u] = 1;
    for (int i = head[u]; i; i = edges[i].nex) {
        int v = edges[i].to;
        if (v == fa || !pd[i]) continue;
        dfs(v, u); root[u] = merge(root[u], root[v]);
        size[u] += size[v];
    }
    for (int i = head[u]; i; i = edges[i].nex) {
        int v = edges[i].to;
        if (v == fa || pd[i]) continue;
        t[++cnt] = (node){v, 0, 0, cnt, 0, dis[u]+dis[v]+edges[i].dis};
        root[u] = merge(root[u], cnt);
    }
    while (check(u, t[root[u]].to)) root[u] = remove(root[u]);
    ans[u] = root[u] ? t[root[u]].val-dis[u] : - 1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
    }
    dijkstra();
    for (int i = 1; i <= n; ++i)
        for (int j = head[i]; j; j = edges[j].nex)
            if (dis[edges[j].to] == dis[i]+edges[j].dis) pd[j] = 1;
    cnt = n; dfs(1, 0);
    for (int i = 2; i <= n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

THANK YOU FOR READING THIS!