枚举+最短路
枚举最低等级,保证酋长在交易范围,然后求最短路。
#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 阅读(195)
评论(0) 编辑 收藏 引用 所属分类:
图论