HDU 2544 最短路

最短路
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 22174 Accepted Submission(s): 9436

Problem Description
在每年的校賽裡，所有進入決賽的同學都會獲得一件很漂亮的t-shirt。但是每當我們的工作人員把上百件的衣服從商店運回到賽場的時候，卻是非常累的！所以現在他們想要尋找最短的從商店到賽場的路線，你可以幫助他們嗎？

Input
輸入包括多組數據。每組數據第一行是兩個整數N、M（N<=100，M<=10000），N表示成都的大街上有幾個路口，標號為1的路口是商店所在地，標號為N的路口是賽場所在地，M則表示在成都有幾條路。N=M=0表示輸入結束。接下來M行，每行包括3個整數A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A與路口B之間有一條路，我們的工作人員需要C分鐘的時間走過這條路。
輸入保證至少存在1條商店到賽場的路線。

Output
對於每組輸入，輸出一行，表示工作人員從商店走到賽場的最短時間

Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output
3
2

思路：采用 Dijistra 算法求最短路徑

import java.util.*;
import java.io.*;
public class Main {
	public static int M=102;
	public static int MAX=2000000;
	public static int map[][]=new int[M][M];
	public static LinkedList<Integer> list;
	public static int n,m;
	public static void main(String[] args) {
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		
		while(sc.hasNextInt()){
			// 初始化 地圖
			for(int i=0;i<M;i++){
				for(int j=0;j<M;j++){
					map[i][j]=MAX;
				}
			}
			list=new LinkedList<Integer>();//從路口是商店所在地到各個路口之間的距離
			n=sc.nextInt();
			m=sc.nextInt();
			if(n==0&&m==0) System.exit(0);//輸入n==0和m==0 結束程序
			for(int i=0;i<m;i++){
				int a=sc.nextInt();
				int b=sc.nextInt();
				int time=sc.nextInt();
				if(map[a][b]>time)
					map[a][b]=map[b][a]=time;//同一條路來回走的時間是相同的
			}
			getDistance(1);
			System.out.println(list.get(n));
		}
	}
	
	//Dijistra 算法
	public static void getDistance(int v){
		int k=0;
		boolean[] boo=new boolean[M];//標志路口是否走過
		for(int i=0;i<=n;i++){
			list.add(map[v][i]);
		}
		boo[v]=true;//true表示已走過的路
		list.set(v,0);
		//判斷各個路口
		for(int i=0;i<=n;i++){
			int min=MAX;
			// 尋找到各個路口，所用最短的時間
			for(int j=0;j<=n;j++){
				if(!boo[j]&&list.get(j)<min){
					min=list.get(j);
					k=j;
				}
			}
			boo[k]=true;
			if(min==MAX) break;
			//到一個新的路口，重新判斷它到各個路口所用的時間
			for(int j=0;j<=n;j++){
				if(!boo[j]&&list.get(j)>list.get(k)+map[k][j]){
					list.set(j,list.get(k)+map[k][j]);
				}
			}
		}
	}
}