HDu2680(Choose the best route) – JAVA編程語言程序開發技術文章

[java]
package graph_ShortestPath; 
 
//思路:構建反向圖。 
import java.util.*; 
import java.io.*; 
public class HDU2680 { 
 
    static int[][]map; 
    static int[]dist; 
    static int n; 
    public static void main(String[] args) throws IOException { 
        //Scanner sc = new Scanner(System.in); 
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); 
        int m,s; 
         
        while(st.nextToken()!=StreamTokenizer.TT_EOF){ 
            n = (int)st.nval; 
            st.nextToken(); 
            m = (int)st.nval;  
            st.nextToken(); 
            s = (int)st.nval; 
            map = new int[n+1][n+1]; 
            for (int i = 1; i <= n; i++) 
                Arrays.fill(map[i], Integer.MAX_VALUE); 
            dist = new int[n+1]; 
             
            for(int i = 0;i<m;i++){ 
                st.nextToken(); 
                int p = (int)st.nval; 
                st.nextToken(); 
                int q = (int)st.nval; 
                st.nextToken(); 
                int t = (int)st.nval; 
                if(t<map[q][p]) 
                    map[q][p] = t;//反向圖。 
            } 
            st.nextToken(); 
            int num =(int)st.nval; 
            int min = Integer.MAX_VALUE; 
            int[]arr = new int[num+1]; 
            for(int i = 1;i<=num;i++){ 
                st.nextToken(); 
                arr[i] =(int)st.nval; 
            } 
             
            dijkstra(s); 
            for(int i = 1;i<=num;i++){ 
                if(dist[arr[i]]<min) 
                    min = dist[arr[i]]; 
            } 
            if(min>=Integer.MAX_VALUE)System.out.println(-1); 
            else System.out.println(min); 
             
        } 
 
    } 
    private static void dijkstra(int ss) { 
        boolean[] p = new boolean[n+1]; 
        for(int i = 1;i<=n;i++){ 
            p[i] = false; 
            if(i!=ss)dist[i] = map[ss][i]; 
        } 
        p[ss] = true; 
        dist[ss] = 0; 
         
        for(int i = 0;i<n-1;i++){ 
            int min = Integer.MAX_VALUE; 
            int k = -1; 
            for(int j = 1;j<=n;j++){ 
                if(!p[j] && dist[j]<min){ 
                    min = dist[j]; 
                    k = j; 
                } 
            } 
            if(k==-1)return; 
            p[k] = true; 
            for(int j = 1;j<=n;j++){ 
                if(!p[j] && map[k][j]!=Integer.MAX_VALUE && dist[j] > dist[k] +map[k][j]) 
                    dist[j]=dist[k]+map[k][j]; 
            } 
        } 
         
    } 
 

 
 

發佈留言