#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=(1<<30)-1;

int main()
{
	int M,N;
	int rank[101];
	int v[101];
	int dis[101][101];
	int result[101];
	int record[101]={0};
	int i,j,k;


	scanf("%d%d",&M,&N);
	for (i=0;i<=N;i++)
		for (j=0;j<=N;j++)
			dis[i][j]=maxn;
	for (i=1;i<=N;i++)
	{
		int k,num,price;
		scanf("%d%d%d",&v[i],&rank[i],&k);
		for (j=1;j<=k;j++)
		{
			scanf("%d%d",&num,&price);
			dis[i][num]=price;
		}
	}


	int total;
	int minn=v[1];
	for (k=2;k<=N;k++)
	{

		memset(record,0,sizeof(record));
		int x;
		if (abs(rank[1]-rank[k])>M)
			continue;
		for (x=1;x<=N;x++)
		{
			if (abs(rank[k]-rank[x])>M || abs(rank[1]-rank[x])>M)
			  record[x]=1;
		}
	  for (i=1;i<=N;i++)
		  result[i]=dis[1][i];
	  int pos=1;
	  int min;
	  record[1]=1;
	  while (pos!=k)
	  {
	    min=maxn;
	    for (i=1;i<=N;i++)
	    {
	  	  if (!record[i] && result[i]<min)
	  	  {
	  	  	min=result[i];
	  	  	pos=i;
	  	  }
	    }
	    record[pos]=1;

	    if (min==maxn)
	  	  break;
	    for (i=1;i<=N;i++)
	    {
	  	  if (!record[i] && min+dis[pos][i]<=result[i] )
	  	  {
	  		  result[i]=min+dis[pos][i];
	  	  }
	    }
	  }

	  total=0;
    total+=result[k];
    total+=v[k];
    if (total<minn)
    	minn=total;
	}
	if (minn==maxn)
		printf("%d\n",v[1]);
	else
	  printf("%d\n",minn);
	return 0;
}

• Re:我已经被WA脑残了。求解释。 (1644) 14310320738 2016-07-22 10:23:51