bool bellman_ford()
{
	bool flag;
	int i,j;
	memset(dis,0,sizeof(dis));
	for(i=0;i<n;i++)				//奇怪，这个循环要执行n次才ac，n-1次就wa 
	{
		flag=false;
		for(j=1;j<=m;j++)
		{
			if(dis[e[j].u]+e[j].w<dis[e[j].v])
			{
				dis[e[j].v]=dis[e[j].u]+e[j].w;
				flag=true;
			}
		}
		if(!flag)	
			return false;
	}
	for(i=1;i<=m;i++)
	{
		if(dis[e[i].u]+e[i].w<dis[e[i].v])
			return true;
	}
	return false;
}

• Re:为什么我的bellman_ford 对所有的边松弛操作时要执行|V|次，|V|-1次就WA？ (12) soonyu 2009-09-19 20:31:34