描述
就是求两对点之间 (s1,t1 和 s2,t2) 最短路的最长重合距离
分析
- 首先要有可以快速判断一条边是否在最短路上的方法, 可以用SPFA分别跑出以s1, t1, s2, t2四个点为起点的单源最短路, 判断时例如如果 d_s1[u] + d_t1[e.to] + e.dist == d_s1[t1], 那么边就在s1, t1的最短路上.
- 确定一些在最短路上的边后就可以用拓扑排序求出最长路. 注意把s2, t2反过来再做一次
- 拓扑排序时注意判断点有没有在最短路上
代码
BZOJ-1880-Elaxia的路线-SDOI2009-SPFA+拓扑排序
原文：http://blog.csdn.net/qq_21110267/article/details/44565803
