题目
Description
Floyd-Warshall算法是求一个图中任意两点之间的最短路径长度的算法。
给出一个有向图，请计算图中任意两个顶点之间的最短路径，及其长度。
Input
单测试用例。
第一行是该有向图的 顶点数n ( 0 < n < 500 )（注：图有n个顶点，首个顶点的编号是0。 ）
第二行是该有向图的 边数e ( 0 < e < n×n )
接下来e行，每行三个整数 i 、j 和 k，表示 顶点i 到顶点j 有一条弧，长度为k。 ( 0 ≤ i, j < n )
（注：输入数据中不含 自环 。）
接下来一个正整数Q，表示有Q个询问。
接下来Q行，每行两个非负整数u和v，表示询问 顶点u 到 顶点v 的最短路长度，以及该最短路径是怎么走的。
Output
对每个询问输出三行。
第一行是一个整数，表示顶点u到顶点v的最短路长度。如果不可达，输出INF ，且不用输出第二行。如果路径长度为0，也不用输出第二行。
第二行是若干个整数，每个整数后面跟一个空格，表示顶点u 到顶点v 的最短路的顶点序列。
第三行是一个空行，仅起分隔作用。
Sample Input
3
5
0 1 4
0 2 11
1 0 6
1 2 2
2 0 3
3
0 2
0 1
1 0
Sample Output
6
0 1 2
4
0 1
5
1 2 0
Hint
样例如下图所示
1397_1.png
注意：本题是special judge，但validator没有写得很完美。你的代码输出时如果没有间隔的空行，PE会判为WA
以下是本人的代码
#include
#include
#define MAX 505
typedef struct
{
int edges[MAX][MAX];
int n,e;
}MGraph;
MGraph G;
int D[MAX][MAX],path[MAX][MAX];
int inf=99999999;
void Path(int u,int v)
{
int k;
k=path[u][v];
if(k==-1)
return ;
Path(u,k);
printf("%d ",k);
Path(k,v);
}
void Dispath(int u,int v)
{
if(D[u][v]==inf||D[u][v]==0)
{
printf("INF\n");
}
else
{
printf("%d\n",D[u][v]);
printf("%d ",u);
Path(u,v);
printf("%d\n",v);
}
}
void Floyd(MGraph G)
{
int Q,u,v;
int i,j,k;
for(i=0;i
{
for(j=0;j
{
D[i][j]=G.edges[i][j];
path[i][j]=-1;
}
}
/*for(i=0;i
{
for(j=0;j
printf("%d ",D[i][j]);
printf("\n");
}
printf("\n");*/
for(k=0;k
{
for(i=0;i
{
for(j=0;j
if(D[i][k](D[i][k]+D[k][j]))
{
D[i][j]=D[i][k]+D[k][j];
//printf("%d ",D[i][j]);
path[i][j]=k;
}}
}
/*for(i=0;i<G.n;i++)
{
for(j=0;j<G.n;j++)
printf("%d ",D[i][j]);
printf("\n");
}
printf("\n");
for(i=0;i<G.n;i++)
{
for(j=0;j<G.n;j++)
printf("%d ",path[i][j]);
printf("\n");
}
system("pause");*/
scanf("%d",&Q);
for(i=0;i<Q;i++)
{
scanf("%d %d",&u,&v);
Dispath(u,v);
printf("\n");
}
}
int main()
{
int i,j,k,t;
scanf("%d",&G.n);
scanf("%d",&G.e);
for(i=0;i<G.n;i++)/////////////ÁÚ½Ó¾ØÕó³õʼ»¯
for(j=0;j<G.n;j++)
{
if(i==j)
G.edges[i][j]=0;
else
G.edges[i][j]=inf;
//printf("%d ",G.edges[i][j]);
}
//printf("\n");
//printf("%d",G.e);
//printf("%d\n",INF);
for(t=0;t<G.e;t++)
{
//system("pause");
scanf("%d %d %d",&i,&j,&k);
G.edges[i][j]=k;
}
/*for(i=0;i<G.n;i++)
{
for(j=0;j<G.n;j++)
printf("%d ",G.edges[i][j]);
printf("\n");
}
printf("\n");*/
//printf("text\n");
Floyd(G);
return 0;
}
