1 5
10000 3 2
2 5000
3 5000
3000 4 1
4 400
3000 2 1
4 500
1000 3 1
5 100
100 2 0

1 5
10000 3 2
2 5000
3 5000
3000 2 1
4 500
3000 4 1
4 400
1000 3 1
5 100
100 2 0
这两个数据结果是 5600吧
故意用了一下 spfa 但是不知怎么  就是不过 管理员能不能 给点数据 mabodx@gmail.com
#include<iostream>
#include<cmath>
using namespace std;
 
 
#define e 1000

int map[e][e];
int flag[e];

struct node{
	int r;
	int l;
	int s[e*100];
}q;

int d[e];
int use[e];

void spfa(int m)
{
	int i,n ;
	memset(d,0,sizeof(d));
	memset(use,0,sizeof(use));
	for(i=0; i<=m; i++)
	{
		d[i]=INT_MAX;
	}
	d[0]=0;
	memset(q.s,0,sizeof(q.s));
	q.r=q.l=-1;
	q.s[++q.l]=0;
	use[0]=1;
	while(q.r<q.l)
	{
	 
		int temp=q.s[++q.r];
		use[temp]=0;
		for(i=0;i <=m ;i++)
		{
			if(i!=temp)
			{
				if(  map[temp][i]!=INT_MAX && d[temp]!=INT_MAX )
					if( flag[i]==0 && d[i] > d[temp]+map[temp][i]  )
					{
						 d[i]=d[temp]+map[temp][i];
					 
						if(use[i]==0)
						{	q.s[++q.l]=i;
							use[i]=1;
						}
					}
				 
			}

		}
	}
}

int main()
{
 
#ifndef ONLINE_JUDGE
     freopen("C:\\Users\\admin\\Desktop\\作业\\A C M\\1\\in.txt","r",stdin);
#endif

	int i,n,m;
	scanf("%d%d", &n,&m);
	int p,l,x;
	memset(flag,0,sizeof(flag));
	int temp=0;
	int t;
	int w;
	for(i=0; i<=m; i++)
		for(t=0; t<=m; t++)
		{
			if(t==i) map[t][t]=0;
			else
			map[t][i]=map[i][t]=INT_MAX;
		}
	for(i=1; i<=m; i++)
	{
		 
		scanf("%d%d%d",&p,&l,&x);
		if(i==1) temp=l;
		
		if(abs( l-temp+0.0)> n )
		{ flag[i]=1; }

		map[0][i]=p;
		for(t=0; t<x ;t++)
		{
			scanf("%d%d", &w,&p);
			map[w][i]=p;
			 
		} 
		 
	}
	spfa(m);
	printf("%d\n", d[1]);
}

• Re:discuss里测试的数据都过了 ，有些ac的程序是错的吧，这个数据明明测某些ac的程序是不对的 (1951) JokerKS 2010-07-03 14:18:09
• Re:discuss里测试的数据都过了 ，有些ac的程序是错的吧，这个数据明明测某些ac的程序是不对的 (47) chouy 2011-05-11 15:42:39
• Re:discuss里测试的数据都过了 ，有些ac的程序是错的吧，这个数据明明测某些ac的程序是不对的 (15) 10226001 2011-08-02 13:25:04