该博客介绍了如何解决一个NOIP模拟赛中的问题，涉及图论和最短路径算法。在一座有100个城市、1000条单向道路的图中，求出在最坏情况下从城市1到城市2的最短距离。如果无法到达城市2，则输出-1。博主提供了一个策略，并解释了最坏情况下最短距离的计算方法，通过枚举和动态规划求解wor[u]和d[i]，最终得到答案。
题目描述
一个国家处于战争状态，一个信使士兵必须使用公路系统从城市1到城市2传递一些非常重要的情报，公路系统完全由单向道路组成。
当士兵开始执行任务时，他被一名特工告知，敌人已经摧毁了该国的一条公路。不幸的是，公路被毁是未知的。信使不知道哪条公路被毁，直到他到达了被摧毁的高速公路的起点。
这名士兵想要使用一种策略，能让他在最坏情况下所走的路尽可能地短
求出最短距离。如果最坏情况下走不到城市2，则输出-1。
输入格式
第1行：2个整数N（N≤100）和M（M≤1000），N表示城市的数量，M表示单向公路的数量
接下来M行，每行3个整数a, b, c，表示城市a和b之间有一条长度为c的单向道路。城市编号1..N
输出格式
第1行：1个整数，答案
输入样例
3 3
1 2 1
1 3 2
3 2 3
输出样例
5
样例说明
最好的策略是，如果第一条道路没有被摧毁，那么就采取1 - > 2的路径。否则，走路径1 - > 3 - > 2。
题解
考虑图G中的一条边（u，v）。当人走到顶点
最低0.47元/天 解锁文章
扫一扫
评论
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
查看更多评论
添加红包
