存图 注意读题，如果小明想要从 iii 号城市跳到 jjj 号城市，则必须保证 i∈a,j∈ai \in a,j \in ai∈a,j∈a。所以要用一个 vis 数组来存储某点 iii 是否 ∈a\in a∈a。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DP 如何计算最少需要旅游多少城市呢？考虑 dpdpdp。 dp[i]dp[i]dp[i] 表示到点 iii 最少需要旅游多少城市。 显然，如果 i∉ai \notin ai∈/a，则 dp[i]=inf⁡dp[i]=\infdp[i]=inf，如果 iii 为起点，则 dp[i]=1dp[i]=1dp[i]=1。 接下来就是方程了，dp[i]dp[i]dp[i] 从何而来？显然，如果与 iii 连边且已经计算过的点就是可能的点。我们要在所有的点中找到旅游城市数量最少的点 jjj。 所以说，状态转移方程式为： dp[i]=dp[j]+1dp[i]=dp[j]+1 dp[i]=dp[j]+1 最终答案就为 dp[dp[dp[终点]]]，即 dp[a[t]]dp[a[t]]dp[a[t]]。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总体评价 该算法的时间复杂度为 O(n+m)O(n+m)O(n+m)。 运行时间：37 ms. 占用内存：14.50MB. 比 bfs 解法好 114514 倍。 AC code:AC\ code:AC code: 完结撒花！