首页 > 代码库 > 九度1008,最短路径问题
九度1008,最短路径问题
时间限制:1 秒
内存限制:32 兆
特殊判题:否
提交:5119
解决:1631
- 题目描述:
- 给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
- 输入:
- 输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
- 输出:
- 输出 一行有两个数, 最短距离及其花费。
- 样例输入:
3 2 1 2 5 6 2 3 4 5 1 3 0 0
- 样例输出:
9 11
- 来源:
- 2010年浙江大学计算机及软件工程研究生机试真题
AC
import java.util.Arrays; import java.util.Scanner; public class J1008_2 { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int m = cin.nextInt(); while (n != 0 && m != 0) { int[][] map = new int[n + 5][n + 5]; for (int i = 0; i < n + 5; i++) Arrays.fill(map[i], Integer.MAX_VALUE / 3); int[][] w = new int[n + 5][n + 5]; for (int i = 0; i < n + 5; i++) Arrays.fill(w[i], Integer.MAX_VALUE / 3); for (int i = 1; i <= m; i++) { int a = cin.nextInt(); int b = cin.nextInt(); int c = cin.nextInt(); int d = cin.nextInt(); map[a][b] = c; map[b][a] = c; w[a][b] = d; w[b][a] = d; } int s = cin.nextInt(); int t = cin.nextInt(); int[] d = new int[n + 5]; Arrays.fill(d, Integer.MAX_VALUE); int[] co = new int[n + 5]; Arrays.fill(co, Integer.MAX_VALUE); boolean[] fa = new boolean[n + 5]; Arrays.fill(fa, true); fa[s] = false; for (int i = 1; i <= n; i++) { d[i] = map[s][i]; co[i] = w[s][i]; } for (int i = 1; i < n; i++) { int min = Integer.MAX_VALUE; int k = 0; for (int j = 1; j <= n; j++) { if (fa[j] && (min > d[j] || (min == d[j] && co[k] > co[j]))) { min = d[j]; k = j; } } fa[k] = false; for (int j = 1; j <= n; j++) { if (fa[j] && (d[k] + map[k][j] < d[j] || (d[k] + map[k][j] == d[j] && co[k] + w[k][j] < co[j]))) { d[j] = d[k] + map[k][j]; co[j] = co[k] + w[k][j]; } } } System.out.println(d[t] + " " + co[t]); n = cin.nextInt(); m = cin.nextInt(); } } }
之前用了佛洛依德超时了,改成C也超时了,于是用了Dijkstra,Dijkstra和Prim很像,Dijkstra是通过节点k来更新d[j],即:d[j] = d[k] + map[k][j];
而Prim是用刚加入最小生成树的节点k到j的距离来更新节点j到原最小生成树的距离,即d[j]=map[k][j]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。