洛谷 P2934 安全出行Safe Travel
rhdeng
2020-01-13 12:54:35
[传送~](https://www.luogu.org/problemnew/show/P2934)
## 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
```cpp
#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!*