import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		int t, n;
		int[][] a;

		BufferedReader stdin = new BufferedReader(new InputStreamReader(
				System.in));
		StringTokenizer sz = new StringTokenizer(stdin.readLine());
		t=Integer.parseInt(sz.nextToken());
		n=Integer.parseInt(sz.nextToken());
		
		a=new int[n][n];
		for(int i=0;i<n;i++){
			Arrays.fill(a[i], Integer.MAX_VALUE);
		}
		for(int i=0;i<n;i++){
			a[i][i]=0;
		}
		
		for(int i=0;i<t;i++){
			sz=new StringTokenizer(stdin.readLine());
			int from=Integer.parseInt(sz.nextToken())-1;
			int to=Integer.parseInt(sz.nextToken())-1;
			int value=Integer.parseInt(sz.nextToken());
			
			a[from][to]=a[to][from]=value;
		}
		
		Dijkstra dij=new Dijkstra(n,0);
		dij.array=a;
		dij.solve();
		dij.printLength(n-1);
	}
}

class Dijkstra {
	int n, start;
	int[] flag;
	int[] cost;
	int[] path;
	int[][] array;

	public Dijkstra(int n, int start) {
		this.n = n;
		this.start = start;

		flag = new int[n];
		cost = new int[n];
		Arrays.fill(cost, Integer.MAX_VALUE);
		path = new int[n];
	}

	public void solve() {
		for (int i = 0; i < n; i++) {
			if (array[start][i] != Integer.MAX_VALUE) {
				cost[i] = array[start][i];
				path[i] = start;
			} else
				path[i] = -1;
		}

		cost[start] = 0;
		flag[start] = 1;
		for (int i = 0; i < n; i++) {
			int tmp = Integer.MAX_VALUE, u = 0;
			for (int j = 0; j < n; j++) {
				if (flag[j] == 0 && cost[j] < tmp) {
					tmp = cost[j];
					u = j;
				}
			}

			flag[u] = 1;
			for (int j = 0; j < n; j++) {
				if (flag[j] == 0 && array[u][j] < Integer.MAX_VALUE
						&& cost[u] + array[u][j] < cost[j]) {
					cost[j] = cost[u] + array[u][j];
					path[j] = u;
				}
			}
		}
	}

	public void printLength(int end) {
		System.out.print(cost[end]);
	}
}

• 重边呀呀呀呀呀呀呀呀 (2100) 20053565 2008-09-27 21:34:15