学步园

int relax(int a,int b,int val)
{
	if(dis[b]>dis[a]+val)
	{
		dis[b]=dis[a]+val;
		path[b]=a;
		return 1;
	}
	return 1;
}
int Bellman()
{
	for(int i=1;i<=N;i++)
	{
		dis[i]=inf;
	}
	dis[sta]=0;
	for(int i=1;i<N;i++)
	{
		int temp=0;
		for(int j=1;j<=M;j++)//无向图的话 是2*M
		{
			if(relax(e[j][0],e[j][1],e[j][2]))
				temp=1;
		}
		if(!temp)
			break;
	}
	for(int i=1;i<=M;i++)
	{
		if(relax(e[i][0],e[i][1],e[i][2]))
			flag=1;
	}
	return dis[end];
}