最短路 Floyd算法 7-4 哈利·波特的考试

#include

#define INF 0x3fffffff

int mp[108][108];
int N,M;

void Floyd()
{
    for (int k = 1;k<=N;k++)
        for (int i = 1;i<=N;i++)
            for (int j = 1;j<=N;j++)
            {
                if(mp[i][j]>mp[i][k]+mp[k][j] && mp[i][k]!=INF && mp[k][j]!=INF)
                {
                    mp[i][j] = mp[i][k]+mp[k][j];
                }
            }
}
int vis[108];
void DFS(int s)
{
    if (!vis[s]) vis[s] = 1;
    for (int i = 1;i<=N;i++)
    {
        if (mp[s][i] != INF && !vis[i]) DFS(i);
    }
}
int main()
{
    
    scanf ("%d%d",&N,&M);
    for (int i = 0;i<=N;i++)
        for (int j = 0;j<=N;j++)
        {
            mp[i][j]=INF;
            if (i==j) mp[i][j]=0;//自己到自己距离为0
        }
            
    while (M--)
    {
        int a,b,c;
        scanf ("%d%d%d",&a,&b,&c);
        mp[a][b] = c;
        mp[b][a] = c;
    }
    DFS(1);//用dfs判断联通图
    for (int i = 1;i<=N;i++) 
    {
        if (vis[i]==0) 
        {
            printf ("0");
            return 0;
        }
    }
    Floyd();
    //这次才对 上面的Floyd都写错了
//      for (int i = 1;i<=N;i++)
//      {
//          for (int j = 1;j<=N;j++)
//         {
//              if (mp[i][j]==INF) printf("0 ");
//             else printf ("%d ",mp[i][j]);
//         }
//          printf ("n");
//      }
    int min = INF;
    int pos;
        for(int i =1;i<=N;i++)
        {
            int max = 0;
            for (int j = 1;j<=N;j++)
            {
                max = max > mp[i][j] ? max : mp[i][j];
            }
            if (min > max)
            {
                min = max;
                pos = i;
            }
        }
    printf ("%d %d",pos,min);
}

//啧啧啧 就是强 想通了之后 一遍过

关键就是考察的Floyd算法，全源最短路问题，需要注意的是，和前面不一样，这里只需要设置一个数组记住图，而修改的过程也是在图上进行的，感觉这样会更好一些，图里面的数据都是存储最短的情况，而这个算法也是非常简单易理解，和动态规划的思路有点像，应该也是取遍所有可能，然后选择性的赋值。

唯一缺点就是复杂度达到O(n*n*n) 基本上200范围内还好说。