Poj(1125)，Floyd，

多源点最短路中的，最长路的，最短路。看到这里就懵逼了，解释一下，找到一个源点，使得路最短，（遍历源点），路最短怎么求呢？就是找到从该源点出发，到达所有点中的最长的点的路径，就是他的最短路，然后根据n个源点，找到这样的最长路最短的，就行了。

这里的具体Floyd算法，我还没推过，dis[i][j]从I到J的最短路。

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

int dis[][];

int n;

void floyd()

{

    for(int k=;k<=n;k++)

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);

    int minlength = INF;

    int flag = ;

    for(int i=;i<=n;i++)

    {

        int maxlength = ;

        for(int j=;j<=n;j++)

        {

            if(i!=j&&dis[i][j]>maxlength)

                maxlength = dis[i][j];

        }

        if(minlength>maxlength)

        {

            minlength = maxlength;

            flag = i;

        }

    }

    if(flag)

        printf("%d %d\n",flag,minlength);

    else printf("disjoint\n");

}

int main()

{

    while(scanf("%d",&n),n)

    {

        memset(dis,INF,sizeof(dis));

        for(int i=; i<=n; i++)

        {

            int pairs;

            scanf("%d",&pairs);

            for(int j=; j<=pairs; j++)

            {

                int to,time;

                scanf("%d%d",&to,&time);

                dis[i][to] = time;

            }

        }

        floyd();

    }

    return ;

}

巴特西

Poj(1125)，Floyd，

最新文章

热门文章