40-最短路

　　　　　　　　　　　　　最短路

问答问题反馈

编辑代码

•  100%
•  1000ms
•  131072K

 

在每年的比赛里，所有进入决赛的同学都会获得一件很漂亮的 t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

输入格式

输入包括多组数据。

每组数据第一行是两个整数 NN、MM（N le 100N≤100，M le 10000M≤10000），NN 表示大街上有几个路口，标号为 11 的路口是商店所在地，标号为 NN 的路口是赛场所在地，MM 则表示在成都有几条路。N=M=0N=M=0 表示输入结束。接下来 MM 行，每行包括 33 个整数 AA，BB，CC（1 le A,B le N,1 le C le 10001≤A,B≤N,1≤C≤1000），表示在路口 AA 与路口 BB 之间有一条路，我们的工作人员需要 CC 分钟的时间走过这条路。

输入保证至少存在 11 条商店到赛场的路线。

输出格式

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。

输出时每行末尾的多余空格，不影响答案正确性

样例输入复制

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

样例输出复制

3
2

import java.util.Scanner;

public class Main {
	public static int[][] map = new int[105][105];
	public static int[] visit = new int[104];
	public static int n, m;
	public static int MAX = 0x3f3f3f3f;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin = new Scanner(System.in);
		n = cin.nextInt();
		m = cin.nextInt();
		while (n != 0 && m != 0) {
			for(int i = 1; i <= n; i++) {
				visit[i] = 0;
				for(int j = 1; j <= n; j++) {
					map[i][j] = MAX;
				}
			}
			for(int i = 0; i < m; i++) {
				int a, b, c;
				a = cin.nextInt();
				b = cin.nextInt();
				c = cin.nextInt();
				if(map[a][b] > c)
					map[a][b] = map[b][a] = c;
			}
			System.out.println(dij(1));
			n = cin.nextInt();
			m = cin.nextInt();
		}
		
	}
	public static int dij(int s) {
		int ans = 0;
		int dist[] = new int[n+1];
		for(int i = 1; i <= n; i++) {
			dist[i] = map[s][i];
		}
		dist[s] = 0;
		for(int i = 0; i < n; i++) {
			int min = MAX;
			int p = 0;
			for(int j = 1; j <= n; j++) {
				if(visit[j] == 0 && min > dist[j]) {
					min = dist[j];
					p = j;
				}
			}
			if(p == 0) {
				break;
			}
			visit[p] = 1;
//			ans += min;
			for(int j = 1; j <= m; j++) {
				if(visit[j] == 0 && dist[j] > map[j][p] + min) {
					dist[j] = map[j][p] + min;
				}
			}
		}
//		return ans;
		return dist[n];
	}

}