Descrpition:

给定一个S-T无向图，询问删掉边(u,v)之后的最短路是多少

Solution:

求出以S为源的最短路径图GraphS(每个点的最短路为disS[])，与以T为源的最短路径图GraphT(每个点的最短路为disT[])

1.对于GraphS，建新图跑网络流，如果Flow >= 2显然怎么删边答案都是原图的最短路，直接GG

2.如果Flow == 1了，那么删掉割边的时候会对答案有影响。

我们用求SCC的方法判断割边，求出个割边显然可以从S到T一字排开，设为Cut(i)，共有K个

我们把残余网络建新图，割边边权设为1，非割边边权设为0，跑以S为源最短路径图GraphS1(DisS[])与以T为源的最短路径图GraphT1(DisT[])

对于一个点u，在GraphS1中，它显然经过Cut(1) .. Cut(DisS[u])。在GraphT1中，它显然经过Cut(K - DisT[u] + 1) .. Cut(K)。

对于每个割边，我们删掉之后，显然要走其他的非割边，现在我们考虑每个非割边(u,v)，经过该边的最短路disS[u]+w(u,v)+disT[v]可以更新的割边的答案显然是Cut(DisS[u]+1) .. Cut(K - DisT[v])这么多

可以用MultiSet或者线段树维护。

Analysis:

用SCC求割边的方法见http://joishbader.is-programmer.com/posts/44453.html。

Hint:

八中上老是RE。。怎么回事= =

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue> 
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int MAXM = 1600010, MAXN = 400010;
const LL inf = 1LL << 60;
struct Eg
{
	int u, v, z, id; Eg *ne, *ep; LL c;
} e[MAXM], *G = e, *po[MAXN], *pre[MAXN];
struct Tseg
{
	int L, R; LL w, tag; Tseg *lch, *rch;
	void Build(int l, int r)
	{
		tag = w = inf;
		if((L = l) == (R = r)) return;
		int mid = (L + R) / 2;
		(lch = new Tseg()) -> Build(L, mid);
		(rch = new Tseg()) -> Build(mid+1, R);
	}
	void push()
	{
		if(lch) lch->tag = min(lch->tag, tag);
		if(rch) rch->tag = min(rch->tag, tag);
		w = min(w, tag); tag = inf;
	}
	void Modify(int l, int r, LL v)
	{
		if(l > r) return; 
		if(L == l && R == r) { tag = min(tag, v); return; }
		if(L != R) push(); int mid = (L + R) / 2;
		if(l > mid) rch -> Modify(l, r, v); else
		if(r <=mid) lch -> Modify(l, r, v); else
		lch -> Modify(l, mid, v), rch -> Modify(mid+1, r, v);
	}
	LL Query(int x)
	{
		if(L == x && R == x) return w = min(w, tag);
		push(); return x > (L + R) / 2 ? rch -> Query(x) : lch -> Query(x);
	}
} *Tree; 
bool f[MAXN], Cut[MAXN], vis[MAXN];
int N, M, Q, tot, cnt, top, S, T, Be, flow, K;
LL C[MAXN], diss[MAXN], dist[MAXN], ans[MAXN], Diss[MAXN], Dist[MAXN];
int A[MAXN], B[MAXN], Que[MAXN], map[MAXN], qsc[MAXN], dfn[MAXN], low[MAXN], belong[MAXN], Map[MAXN];
void add(int x, int y, int z, int id)
{
	G->u = x; G->v = y; G->z = z; G->id = id; G->ne = po[x]; G->ep = G+1; po[x] = G++;
	G->u = y; G->v = x; G->z = 0; G->id =  0; G->ne = po[y]; G->ep = G-1; po[y] = G++;
}
void Add(int x, int y, LL c, int id) { G->v = y; G->id = id; G->c = c; G->ne = po[x]; po[x] = G++; }
void Dij(int s, LL dis[])
{
	priority_queue<PLI, vector<PLI>, greater<PLI> > q;
	for(int i = 1; i <= N; ++i) dis[i] = inf;
	q.push(make_pair(dis[s] = 0, s));
	while(!q.empty())
	{
		int x = q.top().second; q.pop();
		for(Eg *j = po[x]; j; j = j->ne)
		if(dis[j->v] > dis[x] + j->c)
			q.push(make_pair(dis[j->v] = dis[x] + j->c, j->v));
	}
}
int Bfs()
{
	memset(pre, 0x0, sizeof pre);
	memset(vis, 0, sizeof vis); vis[S] = 1;
	int ret = ~0U>>2; queue<int> q; q.push(S);
	while(!q.empty())
	{
		int x = q.front(); q.pop();
		for(Eg *j = po[x]; j; j = j->ne)
		if(j->z > 0 && !vis[j->v]) q.push(j->v), pre[j->v] = j, vis[j->v] = 1;
	}
	for(Eg *zh = pre[T]; zh; zh = pre[zh->u]) ret = min(ret, zh->z);
	for(Eg *zh = pre[T]; zh; zh = pre[zh->u]) zh->z -= ret, zh->ep->z += ret;
	return ret == ~0U>>2 ? 0 : ret;
}
void Dfs(int x)
{
	f[qsc[++top] = x] = dfn[x] = low[x] = ++tot;
	for(Eg *j = po[x]; j; j = j->ne) if(j->z > 0)
		if(!dfn[j->v]) Dfs(j->v), low[x] = min(low[x], low[j->v]);
		else if(f[j->v]) low[x] = min(low[x], dfn[j->v]);
	if(dfn[x] == low[x])
	{
		for(++Be; qsc[top] != x; )
			belong[qsc[top]] = Be, f[qsc[top--]] = 0;
		belong[x] = Be; f[x] = 0; --top;
	}
}
int main()
{
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; ++i)
		scanf("%d%d%d", &A[i], &B[i], &C[i]),
		Add(A[i], B[i], C[i], i), Add(B[i], A[i], C[i], i);
	scanf("%d%d%d", &S, &T, &Q);
	for(int i = 1, a, b; i <= Q; ++i)
	{
		scanf("%d%d", &a, &b);
		for(Eg *j = po[a]; j; j = j->ne) if(j->v == b) { Que[i] = j->id; break; }
	}
	Dij(S, diss); Dij(T, dist);
	for(int i = 1; i <= M; ++i) ans[i] = diss[T];
	memset(po, 0x0, sizeof po); G = e;
	for(int i = 1; i <= M; ++i)
	{
		if(diss[B[i]] == diss[A[i]] + C[i]) add(A[i], B[i], 1, i);
		if(diss[A[i]] == diss[B[i]] + C[i]) add(B[i], A[i], 1, i);
	}
	flow = Bfs() + Bfs();
	if(flow == 1)
	{
		for(int i = 1; i <= N; ++i) if(!dfn[i]) Dfs(i);
		for(int i = 1; i <= N; ++i) for(Eg *j = po[i]; j; j = j->ne)
			if(j->z == 0 && j->id != 0 && belong[i] != belong[j->v]) Cut[j->id] = 1, ++K;
		tot = 0; 
		for(int now = S, temp; now != T; now = temp)
			for(Eg *j = po[now]; j; j = j->ne) if(!j->z && j->id)
				{ temp = j->v; if(Cut[j->id]) map[j->id] = ++tot, Map[tot] = j->id; }
		memset(po, 0x0, sizeof po); G = e;
		for(int i = 1; i <= M; ++i)
		{
			if(dist[B[i]] == dist[A[i]] + C[i]) Add(A[i], B[i], Cut[i], i);
			if(dist[A[i]] == dist[B[i]] + C[i]) Add(B[i], A[i], Cut[i], i);
		}
		Dij(T, Dist);
		memset(po, 0x0, sizeof po); G = e;
		for(int i = 1; i <= M; ++i)
		{
			if(diss[B[i]] == diss[A[i]] + C[i]) Add(A[i], B[i], Cut[i], i);
			if(diss[A[i]] == diss[B[i]] + C[i]) Add(B[i], A[i], Cut[i], i);
		}
		Dij(S, Diss);
		(Tree = new Tseg()) -> Build(1, K);
		for(int i = 1, u, v; i <= M; ++i) if(!Cut[i])
		{
			u = Diss[A[i]] + 1; v = K - Dist[B[i]];
			Tree -> Modify(u, v, diss[A[i]] + dist[B[i]] + C[i]);
			u = Diss[B[i]] + 1; v = K - Dist[A[i]];
			Tree -> Modify(u, v, diss[B[i]] + dist[A[i]] + C[i]);
		}
		for(int i = 1; i <= K; ++i) ans[Map[i]] = Tree -> Query(i);
	}
	for(int i = 1; i <= Q; ++i) if(ans[Que[i]] == inf) puts("Infinity"); else cout << ans[Que[i]] << endl;
	return 0;
}