【先祝贺一下@Jollwish神犇进入CMO国家集训队……合肥OI人总算出了个国家集训队员（虽然不是OI的）……】
最近捉了两道猥琐题……都是有关图中删去某边后的最短路径的问题……核心思想几乎相同……但是，它们很明显是综合题，代码量太大了（与NOIP2012的drive和blockade有得一拼……），因此，从这之中可以得出综合题的一些应对方法。
【1】[Usaco2009 Jan]安全路经Travel
一个无向图，从源点s到每个点的最短路唯一，求对于每个点i，若将图中从s到i的最短路上的最后一条边删除，从s到i的最短路是多少。
由于最短路都唯一，所以s开始的SPT是一棵树……
对于非根结点i，将i的父边删除后，树分为两个部分，s所在的部分记为S，i所在的部分（即子树i）记为T。
可以发现，新的图中s到i的路径，必然是从s开始，先在S部分中走连续的一段，再经过一条边进入T部分，再在T部分中走连续的一段到i……
因为，一旦到了T，就不会再回到S了囧（否则可以直接从s沿着树边走到那里，不必从T绕了），又因为每个点都属于S或T，所以必然只有一条边从S到T……
从s开始走连续的一段，必然是走树边的，设走到x，则长度就是根结点s到x的路径长，设为D[x]……
然后，经过一条边(x, y)走到T中的结点y，由于i是T的根，所以接下来必然是从y向上走到i，路径长是D[y]-D[i]……
也就是，从s到i新的最短路长就是min{D[x]+W(x, y)+D[y]}-D[i]，其中(x, y)边满足：x不在子树i中，y在子树i中，(x, y)边不在SPT树上。
因此，只需要求出SPT树后，枚举所有不在树上的边<x, y>（每条无向边拆成两条有向边），它能影响的范围是[y..LCA(x, y))（注意LCA不能算），取最小值，用路径剖分解决即可……
写代码的时候的几个注意点：
（1）（最坑爹的）最短路不能用SPFA，要用Dijk+Heap（PQ无压力）！！！！！！！！！！！！！MS下一题也是如此……
（2）LCA(x, y)不能算，特别是当y是x的祖先的时候，这条边<x. y>不能对任何结点的最小值产生影响，此时计算出的l>r，一定要特判，不能进入线段树操作！！线段树操作中l>r是会爆的！！
（3）注意-1的情况……
代码（本沙茶在线段树那里很明显写傻了，大家知道囧……）
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 100010, MAXM = 200010, INF = ~0U >> 2;
struct edge0 {
int a, b, w, pre, next;
} E0[MAXM + MAXM + MAXN];
struct edge1 {
int a, b, w;
bool operator< (edge1 e0) const {return w > e0.w;}
} E1[MAXM << 1];
struct edge {
int a, b, pre, next;
bool Z;
} E[MAXN << 1];
struct node {
int mr, lch, rch;
} T[MAXN << 1];
int n, m0, m, dist[MAXN], Q[MAXN], pr[MAXN], SZ[MAXN], N, UP[MAXN], DEP[MAXN], tot[MAXN], root[MAXN];
int _V[MAXN], V_tmp[MAXN], l0, r0, v0;
bool vst[MAXN];
struct qnode {
int No, d0;
bool operator< (qnode q0) const {return d0 > q0.d0;}
};
priority_queue <qnode, vector<qnode> > Q0;
void init_d()
{
re(i, n) E0[i].pre = E0[i].next = E[i].pre = E[i].next = i; m0 = m = n;
}
void add_edge0(int a, int b, int w)
{
E0[m0].a = a; E0[m0].b = b; E0[m0].w = w; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
E0[m0].a = b; E0[m0].b = a; E0[m0].w = w; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void add_edge(int a, int b)
{
E[m].a = a; E[m].b = b; E[m].Z = 0; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
int _m, _a, _b, _w;
scanf("%d%d", &n, &_m); init_d();
re(i, _m) {
scanf("%d%d%d", &_a, &_b, &_w);
add_edge0(--_a, --_b, _w);
}
}
int mkt(int l, int r)
{
int N0 = ++N;
if (l < r) {
T[N0].mr = 0; int mid = l + r >> 1;
T[N0].lch = mkt(l, mid); T[N0].rch = mkt(mid + 1, r);
} else T[N0].mr = INF;
return N0;
}
void dm(int No)
{
int _, __;
if (_ = T[No].mr) {
T[No].mr = 0;
if (__ = T[No].lch) T[__].mr = _;
if (__ = T[No].rch) T[__].mr = _;
}
}
void opr0(int l, int r, int No)
{
if (l >= l0 && r <= r0) T[No].mr = v0; else {
dm(No);
int mid = l + r >> 1, lch = T[No].lch, rch = T[No].rch;
if (mid >= l0) opr0(l, mid, lch);
if (mid < r0) opr0(mid + 1, r, rch);
}
}
void visit(int l, int r, int No)
{
if (l == r) V_tmp[l] = T[No].mr; else {
dm(No);
int mid = l + r >> 1;
visit(l, mid, T[No].lch);
visit(mid + 1, r, T[No].rch);
}
}
void prepare()
{
qnode q0; q0.No = q0.d0 = 0; Q0.push(q0); re2(i, 1, n) dist[i] = INF;
int x, y, d0;
while (!Q0.empty()) {
x = Q0.top().No; Q0.pop();
if (!vst[x]) {
vst[x] = 1;
for (int p=E0[x].next; p != x; p=E0[p].next) {
y = E0[p].b; d0 = dist[x] + E0[p].w;
if (d0 < dist[y]) {dist[y] = d0; q0.No = y; q0.d0 = d0; Q0.push(q0);}
}
}
}
re2(i, n, m0) {
x = E0[i].a; y = E0[i].b;
if (dist[x] + E0[i].w == dist[y]) {pr[y] = m; add_edge(x, y);}
}
Q[0] = DEP[0] = 0;
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=E[x].next; p != x; p=E[p].next) {y = E[p].b; Q[++rear] = y; DEP[y] = DEP[x] + 1;}
}
int z, maxsz;
rre(i, n) {
x = Q[i]; SZ[x] = 1; maxsz = -INF;
for (int p=E[x].next; p != x; p=E[p].next) {
y = E[p].b; SZ[x] += SZ[y]; if (SZ[y] > maxsz) {maxsz = SZ[y]; z = y;}
}
if (maxsz > 0) E[pr[z]].Z = 1;
}
re(i, n) vst[i] = 0;
rre2(i, n, 1) {
x = Q[i];
if (E[pr[x]].Z && !vst[x]) {
for (y=x; y && E[pr[y]].Z; y=E[pr[y]].a) vst[y] = 1;
UP[y] = y; tot[y] = DEP[x] - DEP[y] + 1; root[y] = mkt(0, tot[y] - 1);
for (int j=x; j!=y; j=E[pr[j]].a) {UP[j] = y; tot[j] = tot[y]; root[j] = root[y];}
}
}
re(i, n) {_V[i] = INF; if (SZ[i] == 1 && !E[pr[i]].Z) UP[i] = i;}
}
int LCA(int u, int v)
{
while (UP[u] != UP[v]) if (DEP[UP[u]] >= DEP[UP[v]]) u = E[pr[UP[u]]].a; else v = E[pr[UP[v]]].a;
return DEP[u] <= DEP[v] ? u : v;
}
void solve()
{
int x, y, z, _, w0, m1 = 0;
re2(i, n, m0) {
x = E0[i].a; y = E0[i].b; w0 = E0[i].w;
if (dist[x] + w0 != dist[y] && dist[y] + w0 != dist[x]) {
E1[m1].a = x; E1[m1].b = y; E1[m1++].w = dist[x] + dist[y] + w0;
}
}
sort(E1, E1 + m1);
re(i, m1) {
x = E1[i].a; y = E1[i].b; z = LCA(x, y);
if (y == z) continue; else v0 = E1[i].w;
if (SZ[y] == 1 && !E[pr[y]].Z) {_V[y] = v0; y = E[pr[y]].a;}
while (y != z) {
_ = UP[y];
if (DEP[_] <= DEP[z]) {
l0 = DEP[z] - DEP[_] + 1; r0 = DEP[y] - DEP[_];
opr0(0, tot[y] - 1, root[y]); break;
} else {
l0 = 0; r0 = DEP[y] - DEP[_];
opr0(0, tot[y] - 1, root[y]); y = E[pr[_]].a;
}
}
}
re(i, n) vst[i] = 0;
rre2(i, n, 1) {
x = Q[i];
if (E[pr[x]].Z && !vst[y = UP[x]]) {
visit(0, tot[x] - 1, root[x]); vst[y] = 1; _V[y] = V_tmp[0];
for (int j=x, k=tot[x]-1; j!=y; j=E[pr[j]].a, k--) _V[j] = V_tmp[k];
}
}
}
void pri()
{
re2(i, 1, n) if (_V[i] == INF) printf("%d\n", -1); else printf("%d\n", _V[i] - dist[i]);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}
【2】[Violet 6]故乡的梦
给出一个无向图，对于图中的每条边，求出当删掉它后，s-t最短路径。
做完了第【1】题之后，这题的解法就很容易想到了。
先求出这个图从s开始的SPT。显然，删掉它后s-t最短路径改变的边只能是这个SPT上的s-t割边。
考虑简单的情况：SPT是树。此时，s-t路上的一条边<u, v>删掉后，与第【1】题一样，整棵树分成S和T两部分（s在S部分，t在T部分）。新的s-t最短路，必然是先从s沿着树边往下走到一个结点x，再经过一条<x, y>边走到T部分的一个点y，再从y走到t。可以证明，这个y到t的最短路径必然是只经过T部分的点，不会重新回到S部分（否则直接从s走到这里就行了），因此，它必然不会经过<u, v>。
若SPT不是树，由于SPT中不管肿么走都是最短路径，可以求出它的一棵生成树（注意是有向生成树）。
这样，本题的算法就出来了：
<1>求出s与t到每个点的最短距离dist与dist2，建立s开始的SPT，并求其任意一棵有向生成树；
<2>求出SPT中的s-t割边（方法：求出有向生成树后，也就找到了一条s-t最短路，显然SPT中的s-t割边只能在这条最短路上。在SPT中删去这条路径，然后从s开始扫描路径上的每个点i，从i开始遍历删掉路径之后的SPT，若到达了这条路径上的点，维护其最大深度，扫描到点i时，若最大深度小于i（即i之后的点都还没被遍历到），则i的父边是s-t割边，否则不是。为了优化，可以共享vst——不管从哪个点开始，每个点只能被遍历一次），并标记；
<3>在整个图中，枚举所有不在SPT的这棵生成树上的边（不一定不在SPT上！！）<x, y>（一条无向边拆成两条有向边），该边效果值为dist[x]+dist2[y]+边权，影响范围为[LCA(y, t), LCA(x, t))。由于影响范围都在s-t链上，因此就木有必要像【1】一样用路径剖分了，只需线段树即可。
代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
#define LCH(No) (No + 1)
#define RCH(No, l, r) (No + r - l + 2 - ((r ^ l) & 1))
const int MAXN = 200010, MAXM = 200010, MAXQ = 200010, MAXS = 19;
const ll INF = ~0Ull >> 2;
struct edge {
int a, b, w, pre, next;
bool Z;
} _E[MAXM + MAXM + MAXN], E[MAXN << 1];
struct query {
int a, b;
ll res;
} SQ[MAXQ];
struct pqnode {
int No;
ll d0;
bool operator< (pqnode q0) const {return d0 > q0.d0;}
};
ll T[MAXN << 1];
priority_queue <pqnode, vector<pqnode> > PQ;
int n, nq, n0, _m, m, s, t, Q[MAXN], pr0[MAXN], pr[MAXN], DEP[MAXN], ts[MAXN], prs[MAXN][MAXS], l0, r0;
ll dist[MAXN], dist2[MAXN], v0, res[MAXN];
bool vst[MAXN], vst2[MAXN];
void init_d()
{
re(i, n) _E[i].pre = _E[i].next = E[i].pre = E[i].next = i; m = n; if (n & 1) _m = n + 1; else _m = n;
}
void add_edge_(int a, int b, int w)
{
_E[_m].a = a; _E[_m].b = b; _E[_m].w = w; _E[_m].pre = _E[a].pre; _E[_m].next = a; _E[a].pre = _m; _E[_E[_m].pre].next = _m++;
_E[_m].a = b; _E[_m].b = a; _E[_m].w = w; _E[_m].pre = _E[b].pre; _E[_m].next = b; _E[b].pre = _m; _E[_E[_m].pre].next = _m++;
}
void add_edge(int a, int b, int w)
{
E[m].a = a; E[m].b = b; E[m].w = w; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
int m0, a0, b0, w0;
scanf("%d%d", &n, &m0); init_d();
re(i, m0) {scanf("%d%d%d", &a0, &b0, &w0); add_edge_(--a0, --b0, w0);}
scanf("%d%d%d", &s, &t, &nq); s--; t--;
re(i, nq) {scanf("%d%d", &SQ[i].a, &SQ[i].b); SQ[i].a--; SQ[i].b--; SQ[i].res = -1;}
}
void prepare()
{
re(i, n) dist[i] = INF; dist[s] = 0; pqnode q0; q0.No = s; q0.d0 = 0; PQ.push(q0); int x, y; ll d0;
while (!PQ.empty()) {
x = PQ.top().No; PQ.pop();
if (!vst[x]) {
vst[x] = 1;
for (int p=_E[x].next; p != x; p=_E[p].next) {
y = _E[p].b; d0 = dist[x] + _E[p].w;
if (d0 < dist[y]) {q0.d0 = dist[y] = d0; q0.No = y; PQ.push(q0);}
}
}
}
if (dist[t] == INF) {re(i, nq) SQ[i].res = INF; return;}
re(i, n) {dist2[i] = INF; vst[i] = 0;} dist2[t] = 0; q0.No = t; q0.d0 = 0; PQ.push(q0);
while (!PQ.empty()) {
x = PQ.top().No; PQ.pop();
if (!vst[x]) {
vst[x] = 1;
for (int p=_E[x].next; p != x; p=_E[p].next) {
y = _E[p].b; d0 = dist2[x] + _E[p].w;
if (d0 < dist2[y]) {q0.d0 = dist2[y] = d0; q0.No = y; PQ.push(q0);}
}
}
}
re(i, n) vst[i] = 0; vst[s] = 1; Q[0] = s; DEP[s] = 0;
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=_E[x].next; p != x; p=_E[p].next) {
y = _E[p].b;
if (dist[x] + _E[p].w == dist[y] && !vst[y]) {
pr0[y] = p; pr[y] = m; add_edge(x, y, _E[p].w); DEP[y] = DEP[x] + 1; vst[y] = 1; Q[++rear] = y;
}
}
}
int maxdep = 0, z; re(i, n) vst[i] = 0;
n0 = 0; for (x=t; x!=s; x=E[pr[x]].a) {vst2[x] = 1; _E[pr0[x]].Z = _E[pr0[x] ^ 1].Z = 1; ts[n0++] = x;} ts[n0++] = s; vst2[s] = 1;
int _; for (int front=0, rear=n0-1; front<rear; front++, rear--) {_ = ts[front]; ts[front] = ts[rear]; ts[rear] = _;}
re(i, n) {
x = ts[i];
if (maxdep < i) E[pr[x]].Z = 1;
Q[0] = x; vst[x] = 1;
for (int front=0, rear=0; front<=rear; front++) {
y = Q[front];
for (int p=_E[y].next; p != y; p=_E[p].next) if (!_E[p].Z) {
z = _E[p].b;
if (dist[y] + _E[p].w == dist[z] && !vst[z]) {vst[z] = 1; Q[++rear] = z; if (vst2[z] && DEP[z] > maxdep) maxdep = DEP[z];}
}
}
}
re(i, n) if (i == s) prs[i][0] = -1; else {prs[i][0] = E[pr[i]].a; _E[pr0[i]].Z = _E[pr0[i] ^ 1].Z = 1;}
re2(j, 1, MAXS) re(i, n) if ((x = prs[i][j - 1]) == -1) prs[i][j] = -1; else prs[i][j] = prs[x][j - 1];
re2(i, 1, n0 + n0) T[i] = INF;
}
int LCA(int x, int y)
{
if (DEP[x] > DEP[y]) {int _ = x; x = y; y = _;}
int dep0 = DEP[y] - DEP[x]; rre(i, MAXS) if ((1 << i) <= dep0) {y = prs[y][i]; dep0 -= (1 << i);}
if (x == y) return x; else {
rre(i, MAXS) if (prs[x][i] != prs[y][i]) {x = prs[x][i]; y = prs[y][i];}
return E[pr[x]].a;
}
}
int opr(int l, int r, int No)
{
if (l >= l0 && r <= r0) {if (v0 < T[No]) T[No] = v0;} else {
int mid = l + r >> 1;
if (mid >= l0) opr(l, mid, LCH(No));
if (mid < r0) opr(mid + 1, r, RCH(No, l, r));
}
}
void visit(int l, int r, int No, ll minv)
{
ll minv0 = minv; if (T[No] < minv0) minv0 = T[No];
if (l == r) res[l] = minv0; else {
int mid = l + r >> 1;
visit(l, mid, LCH(No), minv0);
visit(mid + 1, r, RCH(No, l, r), minv0);
}
}
void solve()
{
int x, y;
re2(i, (n & 1 ? n + 1 : n), _m) {
x = _E[i].a; y = _E[i].b;
if (!_E[i].Z) {
l0 = DEP[LCA(x, t)] + 1; r0 = DEP[LCA(y, t)];
if (l0 <= r0) {
v0 = dist[x] + _E[i].w + dist2[y];
opr(0, n0 - 1, 1);
}
}
}
visit(0, n0 - 1, 1, INF);
re(i, nq) {
x = SQ[i].a; y = SQ[i].b;
if (vst2[x] && vst2[y]) {
if (DEP[x] + 1 == DEP[y] && E[pr[y]].Z) SQ[i].res = res[DEP[y]];
else if (DEP[y] + 1 == DEP[x] && E[pr[x]].Z) SQ[i].res = res[DEP[x]];
else SQ[i].res = dist[t];
} else SQ[i].res = dist[t];
}
}
void pri()
{
re(i, nq) if (SQ[i].res == INF) puts("Infinity"); else printf("%lld\n", SQ[i].res);
}
int main()
{
init();
prepare();
if (dist[t] != INF) solve();
pri();
return 0;
}