hdu 1385 Minimum Transport Cost （floyd算法）

貌似····················

這個算法深的東西還是很不熟悉！繼續學習！！！！

++++++++++++++++++++++++++++

============================

++++++++++++++++++++++++++++

-------------------------------------------------

============================

#include<stdio.h>

#include<string.h>
#define MAX 10000000
#define N 1001

int a[N][N],b[N],next[N][N];
int n,len;

void floyd()
{
int i,j,k,fee;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
next[i][j]=j;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
if(i==k||a[i][k]==-1)
continue;
for(j=1;j<=n;j++)
{
if(a[k][j]==-1||i==k||j==k)
continue;
fee=a[i][k]+a[k][j]+b[k];
if(a[i][j]==-1||a[i][j]>fee)
{
a[i][j]=fee;
next[i][j]=next[i][k];
}
else if(a[i][j]==fee)
{
if(next[i][j]>next[i][k])
next[i][j]=next[i][k];
}
}
}
}
}
void path(int start,int end)
{
if(end==next[start][end])
printf("%d-->%d\n",start,end);
else
{
printf("%d-->",start);
path(next[start][end],end);
}
}

int main()
{
int i,j,start,end;
while(scanf("%d",&n),n)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=MAX;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
floyd();
while(scanf("%d%d",&start,&end)!=EOF)
{

if(start==-1||end==-1)
break;
printf("From %d to %d :\n",start,end);
if(start==end)//特別注意：當始點與終點相同時的輸出格式！
printf("Path: %d\n",start);
else
{
printf("Path: ");
path(start,end);
}
printf("Total cost : %d\n\n",a[start][end]);
}
}
return 0;

}