#include<iostream>
using namespace std;
const int MAX=100;
const int INF=1<<28;
struct Edge{
	int x,y,w;
};
struct Point{
	int P,L;
	int minlevel,maxlevel;
};
Point point[MAX+1];
Edge edge[MAX*MAX+1];
int n,M,m;
int lowcase[MAX+1];
void init(int start){
	for(int i=1;i<=n;i++)
	{
		lowcase[i]=INF;
		point[i].minlevel=point[i].L-M;
		point[i].maxlevel=point[i].L+M;
	}
	lowcase[1]=0;
}
bool relax(Edge e){
	if(lowcase[e.y]>lowcase[e.x]+e.w&&point[e.y].L>=point[e.x].minlevel&&point[e.y].L<=point[e.x].maxlevel)
	{
		lowcase[e.y]=lowcase[e.x]+e.w;
		point[e.y].minlevel=max(point[e.y].minlevel,point[e.x].minlevel);
		point[e.y].maxlevel=min(point[e.y].maxlevel,point[e.x].maxlevel);
		return true;
	}
	return false;
}
int Bellman_Ford(int start,int end){
	int i,j;
	bool flag;
	init(start);
	for(i=1;i<n;i++)
	{
		flag=false;
		for(j=1;j<=m;j++)
			flag=relax(edge[j]);
		if(!flag)
			break;
	}
	return 1;
}
int main(){
	int i,j;
	int a,b,c,res;
	while(cin>>M>>n)
	{
		m=1;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			point[i].P=a;
			point[i].L=b;
			for(j=1;j<=c;j++)
			{
				scanf("%d%d",&a,&b);
				edge[m].x=i;
				edge[m].y=a;
				edge[m].w=b;
				m++;
			}
		}
		m--;
		Bellman_Ford(1,n);
		res=INF;
		for(i=1;i<=n;i++)
			res=min(res,lowcase[i]+point[i].P);
		cout<<res<<endl;
	}
}

• 只能说数据太弱了，有一组数据就过不了 (135) Eclipse2008 2011-08-14 15:12:11
  • Re:只能说数据太弱了，有一组数据就过不了 (178) cjxk 2011-10-09 13:03:05
    • Re:只能说数据太弱了，有一组数据就过不了 (36) 1120122083 2014-08-01 21:34:24
  • Re:只能说数据太弱了，有一组数据就过不了 (14) sholck 2015-12-01 19:20:01
    • Re:只能说数据太弱了，有一组数据就过不了 (26) bixiongquan 2016-04-12 16:00:11
  • Re:只能说数据太弱了，有一组数据就过不了 (181) 1023086065 2017-05-22 20:49:00