【先祝賀一下@Jollwish神犇進(jìn)入CMO國(guó)家集訓(xùn)隊(duì)……合肥OI人總算出了個(gè)國(guó)家集訓(xùn)隊(duì)員（雖然不是OI的）……】
最近捉了兩道猥瑣題……都是有關(guān)圖中刪去某邊后的最短路徑的問(wèn)題……核心思想幾乎相同……但是，它們很明顯是綜合題，代碼量太大了（與NOIP2012的drive和blockade有得一拼……），因此，從這之中可以得出綜合題的一些應(yīng)對(duì)方法。
【1】[Usaco2009 Jan]安全路經(jīng)Travel
一個(gè)無(wú)向圖，從源點(diǎn)s到每個(gè)點(diǎn)的最短路唯一，求對(duì)于每個(gè)點(diǎn)i，若將圖中從s到i的最短路上的最后一條邊刪除，從s到i的最短路是多少。
由于最短路都唯一，所以s開(kāi)始的SPT是一棵樹(shù)……
對(duì)于非根結(jié)點(diǎn)i，將i的父邊刪除后，樹(shù)分為兩個(gè)部分，s所在的部分記為S，i所在的部分（即子樹(shù)i）記為T。
可以發(fā)現(xiàn)，新的圖中s到i的路徑，必然是從s開(kāi)始，先在S部分中走連續(xù)的一段，再經(jīng)過(guò)一條邊進(jìn)入T部分，再在T部分中走連續(xù)的一段到i……
因?yàn)椋坏┑搅?/span>T，就不會(huì)再回到S了囧（否則可以直接從s沿著樹(shù)邊走到那里，不必從T繞了），又因?yàn)槊總€(gè)點(diǎn)都屬于S或T，所以必然只有一條邊從S到T……
從s開(kāi)始走連續(xù)的一段，必然是走樹(shù)邊的，設(shè)走到x，則長(zhǎng)度就是根結(jié)點(diǎn)s到x的路徑長(zhǎng)，設(shè)為D[x]……
然后，經(jīng)過(guò)一條邊(x, y)走到T中的結(jié)點(diǎn)y，由于i是T的根，所以接下來(lái)必然是從y向上走到i，路徑長(zhǎng)是D[y]-D[i]……
也就是，從s到i新的最短路長(zhǎng)就是min{D[x]+W(x, y)+D[y]}-D[i]，其中(x, y)邊滿足：x不在子樹(shù)i中，y在子樹(shù)i中，(x, y)邊不在SPT樹(shù)上。
因此，只需要求出SPT樹(shù)后，枚舉所有不在樹(shù)上的邊<x, y>（每條無(wú)向邊拆成兩條有向邊），它能影響的范圍是[y..LCA(x, y))（注意LCA不能算），取最小值，用路徑剖分解決即可……
寫(xiě)代碼的時(shí)候的幾個(gè)注意點(diǎn)：
（1）（最坑爹的）最短路不能用SPFA，要用Dijk+Heap（PQ無(wú)壓力）！！！！！！！！！！！！！MS下一題也是如此……
（2）LCA(x, y)不能算，特別是當(dāng)y是x的祖先的時(shí)候，這條邊<x. y>不能對(duì)任何結(jié)點(diǎn)的最小值產(chǎn)生影響，此時(shí)計(jì)算出的l>r，一定要特判，不能進(jìn)入線段樹(shù)操作！！線段樹(shù)操作中l>r是會(huì)爆的！！
（3）注意-1的情況……
代碼（本沙茶在線段樹(shù)那里很明顯寫(xiě)傻了，大家知道囧……）
#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]故鄉(xiāng)的夢(mèng)
給出一個(gè)無(wú)向圖，對(duì)于圖中的每條邊，求出當(dāng)刪掉它后，s-t最短路徑。
做完了第【1】題之后，這題的解法就很容易想到了。
先求出這個(gè)圖從s開(kāi)始的SPT。顯然，刪掉它后s-t最短路徑改變的邊只能是這個(gè)SPT上的s-t割邊。
考慮簡(jiǎn)單的情況：SPT是樹(shù)。此時(shí)，s-t路上的一條邊<u, v>刪掉后，與第【1】題一樣，整棵樹(shù)分成S和T兩部分（s在S部分，t在T部分）。新的s-t最短路，必然是先從s沿著樹(shù)邊往下走到一個(gè)結(jié)點(diǎn)x，再經(jīng)過(guò)一條<x, y>邊走到T部分的一個(gè)點(diǎn)y，再?gòu)?/span>y走到t。可以證明，這個(gè)y到t的最短路徑必然是只經(jīng)過(guò)T部分的點(diǎn)，不會(huì)重新回到S部分（否則直接從s走到這里就行了），因此，它必然不會(huì)經(jīng)過(guò)<u, v>。
若SPT不是樹(shù)，由于SPT中不管腫么走都是最短路徑，可以求出它的一棵生成樹(shù)（注意是有向生成樹(shù)）。
這樣，本題的算法就出來(lái)了：
<1>求出s與t到每個(gè)點(diǎn)的最短距離dist與dist2，建立s開(kāi)始的SPT，并求其任意一棵有向生成樹(shù)；
<2>求出SPT中的s-t割邊（方法：求出有向生成樹(shù)后，也就找到了一條s-t最短路，顯然SPT中的s-t割邊只能在這條最短路上。在SPT中刪去這條路徑，然后從s開(kāi)始掃描路徑上的每個(gè)點(diǎn)i，從i開(kāi)始遍歷刪掉路徑之后的SPT，若到達(dá)了這條路徑上的點(diǎn)，維護(hù)其最大深度，掃描到點(diǎn)i時(shí)，若最大深度小于i（即i之后的點(diǎn)都還沒(méi)被遍歷到），則i的父邊是s-t割邊，否則不是。為了優(yōu)化，可以共享vst——不管從哪個(gè)點(diǎn)開(kāi)始，每個(gè)點(diǎn)只能被遍歷一次），并標(biāo)記；
<3>在整個(gè)圖中，枚舉所有不在SPT的這棵生成樹(shù)上的邊（不一定不在SPT上！！）<x, y>（一條無(wú)向邊拆成兩條有向邊），該邊效果值為dist[x]+dist2[y]+邊權(quán)，影響范圍為[LCA(y, t), LCA(x, t))。由于影響范圍都在s-t鏈上，因此就木有必要像【1】一樣用路徑剖分了，只需線段樹(shù)即可。
代碼：
#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;
}