Java-求最短路径问题（1）普通版Dijkstra求最短路

Java-求最短路径问题（1）普通版Dijkstra求最短路

package zkj;
import java.math.*;



import java.io.*;





import java.math.*;
import java.util.Scanner;
import java.util.Stack;
import java.util.linkedList;
import java.util.Queue;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;



import java.util.Iterator;
import java.util.Comparator; 

public class Zz {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    static final int N = 505;
    static int w[][] = new int[N][N];//存每一个边
    static int dis[] = new int[N]; // 每个点距离原点的距离。
    static int S[] = new int[N]; // 最短路集合
    static int n,m;
    
    public static int Int(String s){
        return Integer.parseInt(s);
    }
    
    public static int Dijkstra(){
       Arrays.fill(dis, 0x3f3f3f3f);
        dis[1] = 0;
        for(int i = 0; i < n; i++){ // 循环n次， 每次找出一个离起点最近的点。
            int t = -1;
            for(int j = 1; j <= n; j++){
                if(S[j] == 0 && (t==-1|| dis[t] > dis[j])){ // 找到一个距离最短的加入S集合。
                
                    t = j;
                }
            }
            
            S[t] = 1;  // 然后通过这个点来缩短原点到达其他点的距离。
            for(int j = 2; j <= n; j++){
                dis[j] = Math.min(dis[j], dis[t] + w[t][j]);
            }
        }    
        
        if(dis[n] != 0x3f3f3f3f) return dis[n];
        else return -1;
    }    

    public static void main(String[] args) throws Exception{
        String s[] = in.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        
        for(int i = 0; i < n; i++)
            Arrays.fill(w[i], 0x3f3f3f3f);
            
        for(int i = 0; i < m; i++){
            String s1[] = in.readLine().split(" ");
            int a, b, c;
            a = Int(s1[0]);
            b = Int(s1[1]);
            c = Int(s1[2]);
            w[a][b] = Math.min(w[a][b],c);
        }
        
        out.write(Dijkstra()+"n");
        out.flush();

                           }
}