# 最短路

Acwing1125 牛的旅行

原题链接:Acwing1125

题目大意:给定两个不连通的牧场,每个牧场内部的牧区连通, 一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。 现在,John想在农场里添加一条路径 , 连接两个原本不连通的牧场,使得连上这条路径后,这个更大的新牧场有最小的直径。 求这个直径。

……

READ MORE

Acwing383 观光

原题链接:Acwing383

题目大意:给定一个连通图,起点$S$终点$F$,要么满足所选路线总路程为 $S $到 $F$ 的最小路程,要么满足所选路线总路程仅比最小路程多一个单位长度。求这样的路径数目。

……

READ MORE