joj1304floyd.txt

图论中求解不含负权环的多源动态规划算法floyd

#include<iostream>
int Ed[35][35],tmp[35][35],tex[35],path[35][35],n;
const int Max=9999999;
void Flody()
{
	int i,j,k;
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
		{	
		tmp[i][j]=Ed[i][j];
		path[i][j]=j;
		}
		for(k=1;k<=n;++k)
			for(i=1;i<=n;++i)
				if(i!=k)
					for(j=1;j<=n;++j)
						if(j!=i&&j!=k&&tmp[i][k]<Max&&tmp[k][j]<Max&&tmp[i][k]+tmp[k][j]+tex[k]<=tmp[i][j])
						{
							if( tmp[i][k]+tmp[k][j]+tex[k]<tmp[i][j] )
							{
								tmp[i][j]=tmp[i][k]+tmp[k][j]+tex[k];
								path[i][j]=path[i][k];
							}
						    if(tmp[i][k]+tmp[k][j]+tex[k]==tmp[i][j]&&path[i][k]<path[i][j])
							{
								path[i][j] = path[i][k];
							}
						}
		
}

int main()
{
	freopen("1304.txt","r",stdin);
	//freopen("1304r.txt","w",stdout);
	int beg,end,i,j;
while(cin>>n,n)
{
	    for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
		{
			cin>>Ed[i][j];
			if(Ed[i][j]==-1)
				Ed[i][j]=Max;
		}
		for(i=1;i<=n;++i)
			cin>>tex[i];
		Flody();
		while(scanf("%d%d",&beg,&end), beg!=-1&&end!=-1 )
		{
			printf("From %d to %d :\nPath: %d", beg, end,beg);
			i=beg;
			while(i!=end)
			{
				printf("-->%d", path[i][end]);
				i=path[i][end];
			}
			printf("\nTotal cost : %d\n\n", tmp[beg][end]);
		}
	
}
return 0;
}