一道C语言面试题求助

是图论的最短路径
用Floyd算法
#include
#include
int k,dis[501][501],path[501][501],line[501];
void Root(int p,int q)
{
if (path[p][q]>0)
{
Root(p,path[p][q]);
Root(path[p][q],q);
}
else
{
line[k]=q;
k++;
}
}
int main()
{
int i,j,m,n,cost;
scanf("%d%d",&n,&m);//有n个站点，m个航班
for(i=1;i<=m;i++)//1表示纽约，n表示洛杉矶
{
scanf("%d%d%d",&j,&k,&cost);//j到k航班的距离
dis[k][j]=dis[j][k]=cost;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(dis[j][i]>0)
for(k=1;k<=n;k++)
if(dis[i][k]>0)
if((dis[j][k]>dis[j][i]+dis[i][k]||dis[j][k]==0)&&j!=k)
{
dis[j][k]=dis[j][i]+dis[i][k];
path[j][k]=i;
}
k=2;
Root(1,n);
printf("Distance:%d\n1",dis[1][n]);
for(j=2;j<=k-1;j++)
printf("->%d",line[j]);
puts("");
}

//用C++可以写得更好
//刚好正在研究这个，要不才没时间给你写