Poj Solution 2387

http://poj.org/problem?id=2387

import java.util.*;   
public class Main{   
    public static void main(String args[]){   
        Scanner in=new Scanner(System.in);   
        int c=0;   
        int t=in.nextInt();//����˳�����WA��N�Σ������������⣡   
        int n=in.nextInt();   
        int dist[]=new int[n+1];//��������ȷ�������С������RE��N�Σ�   
        int[][] w=new int[n+1][n+1];   
        for(int i=1;i<=n;i++){   
            for(int j=1;j<=n;j++){   
                w[i][j]=Integer.MAX_VALUE;   
            }   
        }   
        for(int i=0;i< t;i++){//����}�㼰֮�����   
            int sn=in.nextInt();   
            int en=in.nextInt();   
            c=in.nextInt();   
            if(c< w[sn][en])   
                w[sn][en]=w[en][sn]=c;   
        }   
        dijkstra(n,w,dist);   
        System.out.println(dist[1]);   
    }   
       
    public static void dijkstra(int v ,int[][] a, int[] dist){//���·��dijkstra�㷨   
         int nn = dist.length - 1 ;         
         boolean[] s = new boolean[nn+1];        
               //��ʼ��         
         for(int i = 1; i <= nn; i++)      
             dist[i] = a[v][i];               
         dist[v] = 0;          
         s[v] = true;        
         for(int i = 1; i < nn; i++){          
             int temp =Integer.MAX_VALUE;       
             int u = v;         
             for(int j = 1; j < nn; j++){       
                 if(!s[j] && dist[j] < temp&&dist[j]>0){           
                     u = j;                  
                     temp = dist[j];            
                 }         
             }             
             s[u] = true;  //�ҵ��˵�һ����S�Ľڵ�      
             for(int j = 1; j <= nn; j++)         
                 if(!s[j] &&dist[u]+a[u][j]< dist[j]&& a[u][j] < Integer.MAX_VALUE)   
                         dist[j] =dist[u]+a[u][j];                                    
         }   
    }    
} 

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *