OpenJudge

04:最短路径

总时间限制:
1000ms
内存限制:
1000kB
描述

昨天我们学了最简单的一个算法“多源最短路径”,算法的核心代码就是三个for循环和一个比较语句;

解决这类问题思路如下:

第一步:把每个点之间的路程转化为一个二维数组

第二步:更新存储路程的这个二维数组,直到该数组中数值符合要求

输入
第一行输入两个数m,n,表示有编号为1到m的m个点,有n条边
接下来有n,每行有三个数i,j,k,表示i到j的距离为k
最后输入两个数x,y。求x到y的最短距离
输出
输出只有一行,为x到y的最短距离,
如果x不能到达y则输出noway
样例输入
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
1 4
样例输出
4
提示
i到j的路程不等于j到i的路程,所有的路都是单向的
来源
信息对抗实验室

01,02 上学期数论问题。
03 BFS/DFS搜索。
04 最短路径问题
05 结合上周最小生成树和最短路径的思想:贪心

全局题号
12822
提交次数
21
尝试人数
10
通过人数
7