[NOIP2017] 逛公园 【最短路】【强连通分量】_weixin_30414245的博客

题目分析:

首先考虑无数条的情况。出现这种情况一定是一条合法路径经过了$ 0 $环中的点。那么预先判出$ 0 $环中的点和其与$ 1 $和$ n $的距离。加起来若离最短路径不超过$ k $则输出$ -1 $，否则这些点必定不被经过，接着dp后效性消失。由于每条边转移了$ k $次它的起点到终点的状态，所以总时间复杂度为$ O(n+mk) $，可以通过所有数据。首先考虑无数条的情况。出现这种情况一定是一条合法路径经过了$ 0 $