本文共 2917 字，大约阅读时间需要 9 分钟。

官方题解就在链接右侧的Contest materials栏里面，就不贴了。

同上一篇博客，是大二到大三小学期第三次排位赛的题，是A题。当时有很多人过了这题的，我的思路就是，居然要满足两对点之间的距离各自小于某一个值，这大概是涉及到次小生成树之类的我不懂的算法吧。因为dij看起来完全没有用的样子，floyed又肯定会超时，完全没有去想。

现在想来就是图的基本知识都太薄弱了。比如下午看了几分钟Comet Oj今年年初camp的图论直播，大佬讲了几分钟就讲到了边权只有0和1的图可以用bfs求最短路。你说巧不巧，他讲了这么多我就听懂了这一句话，马上补这个题目就用到了。bfs呀少年。具体的等下放在思路里面讲。

，现在觉得官方题解 + 一篇中文博客来理解是极佳的方法，官方题解纯英文容易看不懂一些语句的意思，中文博客可能缺少官方题解里的一些关键细节（比如上一篇博客里拆分质因数来理解的关键点）。题意就见这个博客吧。

题记里面说了，边权只有0和1的图用bfs就可以求出最短路。只要对顶点出发进行搜索，整张图搜一遍就出来最短路了。这里都没有边权为0的图，所有边都是1。所以O(n)就能求出单源最短路，而任意两点的最短路也是O(n * n)的。当然，盲目求最短路是没有结果的。其实在比赛的时候我有大致靠近这个正确思路，但是想了一点就觉得后面是无法实现的分类讨论，然而其实有简单的考虑方法。

就是分为两种情况，其一，s1到t1，s2到t2，各自为政，互不相关，这两条路线没有相交的地方。这样，所需保留的最少路长就是两对点之间最短路的和。其二，s1到t1，s2到t2，路线有所相交。这样考虑起来是不是变得很麻烦？其实不然，我们只要枚举相交段的两个端点就可以了。会不会出现两条路线相交、分离、再相交的情况？想多了。只要相交，必然只有一段连续的相交段，因为分离开来再相交，分离部分必定是相等的两段，选择一段合并到这一段上就好了。什么， 可能不是相等的？那就不是最短路啦！不可能的！

第一种情况，保留部分为dis[s1][t1] + dis[s2][t2]就可以了。第二种情况，枚举i，j为相交段的两个端点，则第一对点的保留部分应该为min(dis[s1][i] + dis[j][t1], dis[s1][j] + dis[i][[t1]) + dis[i][j]，另一对点同理，因为对于两对点来说，i，j谁是进入点、谁是分离点是不确定的。