解题报告 $2022.10.18$


T1 不稳定的道路题目描述有 nnn 个城市和 mmm 条道路。城市编号 至 ,道路编号 111 到 nnn。道路 iii 双向连接城市 aia_iai​ 和城市 bib_ibi​。但是通过每一条道路,所需的时间却是不稳定的,跟出发的时刻有关,如果在时刻 ttt 通过道路 iii,那么需要的时间为:

[HNOI2014]道路堵塞


题目描述题目传送门思路首先有一个结论:删除边后的最短路一定是在最短路上跑一段,然后跳出最短路,然后再跑一段。换言之,就是不在最短路上跑的路径一定是一段连续的路径,不会存在两段及以上(如果两段相等,假设选择原最短路上的路径)。证明:这个结论是我猜出来的,现在给出简要证明。记 dis⁡(i)\opera