求救贴 女大学生卡死在学校oj题上 求助求助 Floyd-Warshall算法 5C

题目


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;

}

4个回答

女大学生?你男票呢,不能帮你?姐姐是可怜你,给你个链接,自己看吧 http://blog.csdn.net/ll365594480/article/details/6792096

helloyourkey
helloyourkey 此处我竟然笑了很久
一年多之前 回复

#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;
}

这样应该可以了,具体细节请自己修改

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!