Chanyuenlam
Chanyuenlam
采纳率0%
2017-12-29 02:00 浏览 1.1k

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

5

题目


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条回答 默认 最新

  • devmiao devmiao 2017-12-29 03:43

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

    点赞 1 评论 复制链接分享
  • AlphaGo_Zero AlphaGo_Zero 2018-01-02 11:45
     #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;
    }
    
    点赞 1 评论 复制链接分享
  • AlphaGo_Zero AlphaGo_Zero 2018-01-02 11:43

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

    点赞 评论 复制链接分享
  • AlphaGo_Zero AlphaGo_Zero 2018-01-02 11:44

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

    点赞 评论 复制链接分享