这个题在bzoj上好像是个权限题，想做的可以去Vani的博客下载测试数据。
这里有题面。
简单叙述一下题意：
给你一个n个点、m条边的带权无向图，S点和T点，询问Q次删一条给定的边的S-T最短路。
其中 1<=n,m,q<=200000 。
ps. 1.这个题网上好多解法都是错的。2.这个题数据范围很大。
先求S到每个点的距离ds[i]。如果ds[T]为inf的话，输出Q个无解好了。
然后再求每个点到T的距离dt[i]。（用堆优化的Dijkstra即可。）
建一张最短路径图Gs仅包含ds[v]==ds[u]+w[u,v]这样的有向边。
同理再建一张最短路径图Gt仅包含dt[v]==dt[u]+w[u,v]这样的有向边。
我们可以发现在这两张最短路径图上，有一些关键边，与桥边类似，从S-T的最短路必经这些边。
可以知道，如果删掉的不是这些关键边，那么答案不会变，只有删掉关键边答案才会变。
这些关键边如何求呢？网上有些题解写的是把最短路径图看成无向图的桥边。（这个是有明显反例的，随便一拍都是反例，但是有的代码就是能过题 - -|）
还有的是用对Tarjan求桥边的时候做了一些限制，但是我觉得正确性未知。
我用了一种比较保(qi)险(guai)的方法，求出的这些关键边。
首先假设每条边的容量都是1，像网络流一样做两次增广，注意不需完整的最大流，只需两次增广。
如果流量>=2，说明这个图里没有关键边，直接输出Q个ds[T]即可。
那么我们来看流量是1的时候，很显然关键边就是能成为最小割的边（流量只有1），我们用Tarjan对这个图求一次强连通分量，设id[i]表示i这个点所属的连通分量编号。如果一条边(u,v)满流且id[u]!=id[v]那么这条边就可以成为最小割的一条边，即为关键边。
如果把Gs中的关键边反向就是Gt中的关键边。
我们就得到了Gs与Gt中的关键边，这些关键边应该从S到T排成一列，不妨编号为1，2，3…。
我们考虑删除一条关键边(u,v)，如果另一条非最短路图上的边(x,y)跨越了(u,v)那么ds[x]+w[x,y]+dt[y]就可能成为答案，这些(x,y)取min即可。
现在需要判断那些(x,y)可以跨越(u,v)，有用了一种稳(qi)妥(guai)的方法判断的，将Gs,Gt中的边都给一个权值，如果这条边是关键边，那么这条边边权为1，否则这条边边权为0，然后我们在Gs上求一个这个图的最短路记为Ds[i]，同理Dt[i]，注意这里不用Dijkstra或SPFA，因为边权都是0/1所以来一次0/1 bfs即可（双端队列）。
Ds[i]与Dt[i]的意义比较明显，从S到i点最短路经过最少关键边的数量，和从i点到T点最短路经过最少关键边的数量。那么我们就可以判断一条边是否跨过了第num条关键边，即为Ds[x]<num&&Dt[y]<sum-num (sum为关键边总数)。
但是每次枚举所以的边是不可能的，我们可以用离线的思想,预处理出每条关键边的答案。先预处理出Ds[i]值相等的点，可以存进一个vector。然后我们从左向右扫描这些关键边，从左向右扫描时，右端合法状态(Dt[y])是单调递减的，所以可以维护一个小根堆，代表现在可行的决策，堆中的关键字为ds[x]+w[x,y]+dt[y],那么堆顶就是一个最优方案。具体的讲，现在准备算第num条关键边，先把堆顶中Dt[y]>=sum-num的边删去，然后添加vector中Ds[i]==num的所有点的所有出边入堆，然后记录堆顶答案，算下一个num。
然后读入询问判一下是哪条边，输出答案即可。
程序写了不到6k。程序中变量名称对应题解中变量名称。
代码很丑。
https://gist.github.com/zrt/406a99ed44432c589179