//%%%%%dalao
/*******************
*poj.org Prob. 1062*
*Author: Congbo SUN*
*******************/

#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 100;
const int INF = 1000000;
const int INFB = 42;
struct Node
{
    int val;
    int lvl;
};
struct Node nd[MAXN+2];
int f[MAXN+2][MAXN+2];
int ff[MAXN+2][MAXN+2];
int dis[MAXN+2];
bool vis[MAXN+2];
int n,d;
int low,high,base;

void Dijkstra(int start)
{
	int i,j,pos;
	
	for(j=1; j<n; j++)
	{
		pos = -1;
		for(i=1; i<=n; i++)
		{
			if(!vis[i] && (pos == -1 || dis[i] < dis[pos]))
			{
				pos = i;
			}
		}
		if(pos == 0)	break;
		vis[pos] = true;
		for(i=1; i<=n; i++)
		{
			if(dis[pos]+f[pos][i] < dis[i])
			{
				dis[i] = dis[pos]+f[pos][i];
			}
		}
	}
}

int main()
{
    int i,j,k,x,y,z,tmp,ans;

    scanf("%d%d",&d,&n);
    memset(ff,INFB,sizeof(ff));
    for(i=1; i<=n; i++)
    {
        scanf("%d%d%d",&nd[i].val,&nd[i].lvl,&x);
        for(j=1; j<=x; j++)
        {
            scanf("%d%d",&y,&z);
            ff[i][y] = z;
        }
    }
    
    base = nd[1].lvl;
    for(i=0; i<=d; i++)
    {
    	memset(dis,INFB,sizeof(dis));
    	memset(vis,false,sizeof(vis)); 
    	high = base+i;
    	low = high-d;
    	for(j=1; j<=n; j++)
    	{
    		for(k=1; k<=n; k++)
    		{
    			if(nd[j].lvl <= high && nd[j].lvl >= low && nd[k].lvl <= high && nd[k].lvl >= low)	f[j][k] = ff[j][k];
    			else																				f[j][k] = INF+1;
    			if(j == 1)	dis[k] = f[j][k];
    		}
    	}
    	
    	Dijkstra(1);
    	
    	tmp = INF+1;
    	for(j=2; j<=n; j++)
    	{
    		if(dis[j]+nd[j].val < tmp)	tmp = dis[j]+nd[j].val;
    	}
    	if(tmp > nd[1].val)	tmp = nd[1].val;
    	if(tmp < ans)	ans = tmp;
    }
    
    printf("%d\n",ans);

	return 0;
}

• G++ WA, C++ AC。。。 (8) suncongbo 2017-05-20 13:07:35