终于A 了，这题做着真麻烦
题目：http://poj.org/problem?id=1062
dijk 一般用于正权有向图
此题的关键在于等级限制的处理，最好的办法是采用枚举，即假设酋长等级为5，等级限制为2，那么需要枚举等级从3~5,4~6,5~7
题意就不用说了，做poj以来的第一道中文题目。
要考虑间接身份差异不可行的情况
如：1 4
10000 3 2
2 1
3 3
1000 2 2
4 1
3 1
1000 3 1
4 2
100 4 0
错误程序出104,答案105。
对于这组数据错误的程序是4->3->2->1的，但4和2不能并存
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std; int lim[];
const int INF=<<;
int n;
struct no
{
int p,l,x,a[],b[];
} thing[]; struct node
{
int u,v,w,next;
} edge[];
int head[],dis[],cnt;
void add(int u,int v,int w)
{
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
} int dijkstra(int s)
{
int vis[],i,j,min;
for(i=; i<=n; i++)
dis[i]=INF;
memset(vis,,sizeof(vis));
dis[s]=;
for(i=; i<=n; i++)
{
int minn=INF;
int u=s;
for(j=; j<=n; j++)
{
if(!vis[j] && minn>dis[j] &&lim[j]) //lim标记是否在限制条件内
{
minn=dis[j];
u=j;
}
}
for(j=head[u]; j!=-; j=edge[j].next)
{
int v=edge[j].v;
int newdis=minn+edge[j].w;
if(!vis[v] && newdis < dis[v] && lim[v])//lim标记是否在限制条件内
dis[v]= newdis;
}
vis[u]=;
}
min=thing[].p;
for(i=; i<=n; i++) //一组完成后 比较
{
if(dis[i]+thing[i].p<min)
min=dis[i]+thing[i].p;
}
return min;
}
int main()
{
int m,i,j,ans;
scanf("%d%d",&m,&n);
cnt=;
memset(head,-,sizeof(head));
for(i=; i<=n; i++)
{
scanf("%d%d%d",&thing[i].p,&thing[i].l,&thing[i].x);
for(j=; j<=thing[i].x; j++)
{
scanf("%d%d",&thing[i].a[j],&thing[i].b[j]);
}
}
for(i = ; i <= n; i++) //其实我这一步没什么必要，当时想少了，下一步就可以搞定
{
for(j=; j<=thing[i].x; j++)
{
if(abs(thing[i].l-thing[thing[i].a[j]].l)<=m)
add(i,thing[i].a[j],thing[i].b[j]);//倒着建的图
}
}
ans=thing[].p;
for(i=m; i>=; i--)
{
memset(lim,,sizeof(lim));
for(j=; j<=n; j++) //枚举
{
if(thing[j].l>=(thing[].l-i)&&thing[j].l<=(thing[].l+m-i))
lim[j]=;
}
if(dijkstra()<ans)
ans=dijkstra();
}
printf("%d\n",ans);
return ;
}