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;
}
女大学生？你男票呢，不能帮你？姐姐是可怜你，给你个链接，自己看吧 http://blog.csdn.net/ll365594480/article/details/6792096
#include
int n,e,q,p;
int G[501][501],dis[501][501],next[501][501];
const int oo=1<<30;
int main()
{
scanf("%d%d",&n,&e);
int f,t,c,i,j,k;
for(i=0;i<500;i++)
for(j=0;j<500;j++)
dis[i][j]=G[i][j]=oo,next[i][j]=0;
for(i=0;i<e;i++)
{
scanf("%d%d%d",&f,&t,&c);
dis[f][t]=G[f][t]=c;
next[f][t]=t;
}
for(i=0;i<n;i++)
{
dis[i][i]=0;
next[i][i]=i;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
next[i][j]=next[i][k];
}
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d%d",&f,&t);
if(dis[f][t]==oo) printf("INF\n");
else
{
printf("%d\n",dis[f][t]);
p=f;
while(p!=t)
{
printf("%d ",p);
p=next[p][t];
}
printf("%d ",t);
printf("\n");
}
printf("\n");
}
return 0;
}
这样应该可以了，具体细节请自己修改
#include<cstdio>
int n,e,q,p;
int G[501][501],dis[501][501],next[501][501];
const int oo=1<<30;
int main()
{
scanf("%d%d",&n,&e);
int f,t,c,i,j,k;
for(i=0;i<500;i++)
for(j=0;j<500;j++)
dis[i][j]=G[i][j]=oo,next[i][j]=0;
for(i=0;i<e;i++)
{
scanf("%d%d%d",&f,&t,&c);
dis[f][t]=G[f][t]=c;
next[f][t]=t;
}
for(i=0;i<n;i++)
{
dis[i][i]=0;
next[i][i]=i;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
next[i][j]=next[i][k];
}
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d%d",&f,&t);
if(dis[f][t]==oo) printf("INF\n");
else
{
printf("%d\n",dis[f][t]);
p=f;
while(p!=t)
{
printf("%d ",p);
p=next[p][t];
}
printf("%d ",t);
printf("\n");
}
printf("\n");
}
return 0;
}