#include<iostream>
using namespace std;
int m,n;
int money[101],rank[101];
int p[101][101];
bool final[101];
int d[101];
int maxn[101];
int minn[101];
int absol(int a)
{
	if(a>=0)
		return a;
	else
		return -a;
}
void dij(int v)
{
	int i,j,ff,min;
	for(i=1;i<=n;i++)
	{
		d[i]=p[v][i];
		maxn[i]=rank[v]>rank[i]?rank[v]:rank[i];
		minn[i]=rank[v]<rank[i]?rank[v]:rank[i];
		final[i]=false;
	}
	final[v]=true;
	for(i=1;i<n;i++)
	{
		min=200000000;
		for(j=1;j<=n;j++)
		{
			if(!final[j])
			{
				if(d[j]<min&&d[j]!=0)
				{
					min=d[j];
					ff=j;
				}
			}
		}
		final[ff]=true;
		for(j=1;j<=n;j++)
		{
			if(!final[j]&&(min+p[ff][j]<d[j])&&absol(maxn[ff]-rank[j])<=m&&absol(minn[ff]-rank[j])<=m)
			{
				maxn[j]=maxn[ff]>rank[j]?maxn[ff]:rank[j];
				minn[j]=minn[ff]<rank[j]?minn[ff]:rank[j];
				d[j]=min+p[ff][j];
			}
		}
	}
}
int main()
{
	cin>>m>>n;
	int a,b,c,i,j,minnum;
	for(i=1;i<=n;i++)
	{
		cin>>money[i]>>rank[i]>>a;
		for(j=1;j<=a;j++)
		{
			cin>>b>>c;
			p[i][b]=c;
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(p[i][j]==0||absol(rank[i]-rank[j])>m)
				p[i][j]=200000000;
		}
	}
	dij(1);
	minnum=money[1];
	for(i=2;i<=n;i++)
	{
		if(d[i]+money[i]<minnum)
			minnum=d[i]+money[i];
	}
	cout<<minnum<<endl;
	return 0;
}

数据:
10000 3 2
2 1
3 3
1000 2 2
4 1
3 1
1000 3 1
4 2
100 4 0


答案应该是105。

• Re:附上一段错误却ac了的代码，以及数据，希望管理员加强数据 (6) 449554866 2011-02-10 12:49:38