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];
}
}
}