枚举+最短路
枚举最低等级,保证酋长在交易范围,然后求最短路。
#include<iostream>
using namespace std;

const int inf=100000000;
int m,n;
int map[105][105];
int dis[105],vis[105],lev[105];

int dijkstra()


{
int ans=inf;
int i,j,k;
for(i=lev[1]-m;i<=lev[1];i++)

{
memset(vis,0,sizeof(vis));
for(j=1;j<=n+1;j++)
dis[j]=map[1][j];
vis[1]=1;

for(j=1;j<=n;j++)

{
int min=inf,cur=-1;
for(k=1;k<=n+1;k++)

{
if(!vis[k]&&lev[k]>=i&&lev[k]<=i+m&&dis[k]<min)

{
min=dis[k];
cur=k;
}
}
if(cur==-1) break;
vis[cur]=1;

for(k=1;k<=n+1;k++)

{
if(!vis[k]&&lev[k]>=i&&lev[k]<=i+m&&map[cur][k]!=inf&&dis[k]>dis[cur]+map[cur][k])
dis[k]=dis[cur]+map[cur][k];
}
}
if(dis[n+1]<ans)
ans=dis[n+1];
}
return ans;
}

int main()


{
int p,l,x,t,v;
int i,j;
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)

{
if(i==j) map[i][j]=0;
else map[i][j]=inf;
}
for(i=1;i<=n;i++)

{
scanf("%d%d%d",&p,&l,&x);
map[i][n+1]=p;
lev[i]=l;
for(j=1;j<=x;j++)

{
scanf("%d%d",&t,&v);
map[i][t]=v;
}
}
lev[n+1]=lev[1];
printf("%d\n",dijkstra());
return 0;
}
posted on 2010-08-11 16:40
wuxu 阅读(203)
评论(0) 编辑 收藏 引用 所属分类:
图论