Poj Solution 1062

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

//���ձ��˵�˼���õ�,֮ǰ���Ǻ��˽�dijkstra������������Щ��� 
//1,����ǰδ�������·�ķ��Ҫ��ľ�����̽���������·; 
//2,�������뵱ǰ����Ľ���й�j����δ���������·�Ľ����̾�����и��¡� 
//ͼ������һ������С�����ĵľ����㷨Prim�㷨��Dij��̼������ƣ�����̰��˼�롣 
//ֻ��һ���ǶԶ����ѡ������һ���ǶԱߵ�ѡ�� 

import java.util.*; 
public class Main 
{ public static int[][] e; 
   public static int[]  dis; 
   public static int[] used; 
   public static int[] level; 
   public static int n,m; 
   public static void main(String[] args){ 
    Scanner cin = new Scanner(System.in); 
    int  x,t; 
    e = new int[101][101]; 
    dis = new int[101]; 
    used =  new int[101]; 
    level = new int[101]; 
          m=cin.nextInt(); 
          n=cin.nextInt(); 
           for(int i=1;i<=n;i++) 
             {   e[0][i]=cin.nextInt(); 
                 level[i]=cin.nextInt(); 
                  x=cin.nextInt(); 
                for(int j=0;j< x;j++) 
                { t=cin.nextInt(); 
                  e[t][i]=cin.nextInt(); 
                } 
             } 
           solve(); 
} 

public static void solve() 
{ int max,result; 
  result=e[0][1]; 
  for(int i=1;i<=n;i++) 
     { max=level[i]; 
       for(int j=1;j<=n;j++) 
        if(level[j]>max || level[j]< max-m)//�ж����׵��˵ĵȼ��Ƿ�����Ŀ�������� 
         used[j]=1;//����� 
        else 
         used[j]=0; //��� 
       dijkstra(); 
       if(result>dis[1]) //�Ƚ�ÿ������ķ��� 
         result=dis[1]; 
} 
System.out.println(result); 
} 
public static void dijkstra() 
{ int min,temp,k; 
  for(int i=1;i<=n;i++) 
   dis[i]=e[0][i]; 
  for(int i=1;i<=n;i++) 
     { min=0x7FFFFFFF; 
       k=0; 
       for(int j=1;j<=n;j++)//�ҳ�����С�ı� 
         if(used[j]==0 && dis[j]< min) 
          {min=dis[j]; 
              k=j; 
          } 
       if(k==0) 
        break; 
       used[k]=1; 
       for(int j=1;j<=n;j++)//������ڵ��ֵ 
        if(used[j]==0 && e[k][j]>0 && min+e[k][j]< dis[j]) 
         dis[j]=min+e[k][j]; 
    } 
   } 
}