渣题选做

P1629 邮递员送信

正反跑两遍spfa.

正确性：鉴于图中给的边一定是能从1到任意一个点，再从任意一个点回来的有向边，那么反过来建边时1到这个点的最短路就是原图种这个点回到1的最短路，从而不用再跑多源最短路径，极大的节省了时间复杂度。