题目
题目大意
给你一个带权无向图，有起点和终点。然后有许多询问，询问删除某两点之间的边后的最短路。
分析&正解
这题是在某个PPT里看到的，都不知道在哪里可以评测，所以干脆没有打。
看看这题，感觉好像是一个非常经典的题型，可是……想不出来。
有一个思路：建立最短路图。
这个思路还是容易想到的，建立最短路图之后，如果删去的边不在最短路图之内，那么最短路就不变！
我们发现有些点是没有意义的，所以把它们删去。
最后形成的这个最短路图有一些有趣的性质。
先说明一下，这个最短路图还是当成无向图（我们平常建立的最短路图都是有向图）。
发现这个最短路图中有边双，缩点，然后继续观察。
我们会发现缩点之后的图是一条链。
为什么？万一是一棵树呢？
如果是一棵树，
因为这个图有起点和终点，我们假设起点在根节点，那么终点在某个叶子节点中。
由于我们已经在前面删掉了无意义的点，就是不会到终点的点。
那么除了起点到终点的这一条链，其它的分支都是没有意义的，所以会被删去。
这个结论很重要。
显然，如果删去的边在某个边双中，最短路的长度也是不会变的。
现在我们只需要思考，如果删去的是桥边，那么如何计算。
对于这些删去桥边的情况离线计算：
建立一个小根堆堆，存一些边，对于每个边(u,v)(u,v)(u,v)，存入的值为disSu+len(u,v)+disTvdisS_u+len(u,v)+disT_vdisSu+len(u,v)+disTv。
它代表了如果必须走这条边的最短路径。
然后一个一个扫边双，到了某个边双之后，就将所有从先前的边双连向它的边从堆中删去，然后将所有从它连向后面的边双的边加进来。
搞完之后，如果要删去这个边双和下一个边双之间的桥边，那么堆中的最小值就是答案。
为什么这么做？
先不考虑删除边，
如果边(u,v)(u,v)(u,v)不得不经过，为了使得路径长度最小，那么起点到uuu，vvv到终点，这两段的路径一定在最短路图之中。
当一个边双和下一个边双之间的桥断开的时候，我们不能走桥，不得不走其它的路径。
必须要经过某一条跨过中间的边。
所以，我们要将不跨过中间的边，也就是之前的边双连向这个边双的边删去，然后把新的边加进来。
时间复杂度是O((N+M+Q)lgN)O((N+M+Q)\lg N)O((N+M+Q)lgN)，很优秀。
总结
在见到某些类似于动态最短路题目的时候，我们可以想到建立最短路图。
然后注意最短路图在缩点之后会变成一条链（有起点和终点的情况下）。
最后就是想想如何在边双之间处理东西。
感觉上这道题还挺不错，可惜没有地方评测……