poj 1125 FLoyd

淩亂°似流年 2021-11-02 14:26 231阅读 0赞

题意：

让你找一个点，从这个点向其它点传递信息所要的时间最短。输出这个点得编号，和最晚收到信息的人所需时间。

算法：

1.Dijkstra算法一次只能求单源最短路径，而FLoyd算法则可以求出每对顶点得最短路径，求一次则可。

2.枚举每个点到各点的最大直，比较各点的最大直就可以得出答案。这个最大最大直就是最晚收到信息所需时间。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdlib.h>
    #include<string.h>
    #include<stdio.h>
    
    int mp[210][210];
    int N;
    const int inf = 0x7f7f7f7f;
    
    
    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[k][j] != inf && mp[i][j] > mp[i][k] + mp[k][j] && mp[k][j] != inf )
                 mp[i][j] = mp[i][k] + mp[k][j];
     
            }
    
    
    }
    
    void solve( )
    {
      int maxn = inf, ans = 0;
      int minx = 0;
      for( int i = 1; i <= N; i++)
      {
          minx = 0;
        for( int j = 1; j <= N; j++)
        {
          if( mp[i][j] > minx )
             minx = mp[i][j];
    
        }
        if( minx < maxn )
        {
           maxn = minx;
           ans = i;
        }
    
      }
      if( ans == 0 )
        puts("disjoint");
      else
        printf("%d %d\n", ans, maxn);
    
    
    }
    
    int main( )
    {
      int M, a, b;
      while( scanf("%d",&N), N )
      {
        for( int i = 1; i <= N; i++)
        for( int j = 1; j <= N; j++)
            mp[i][j] = ( i == j ) ? 0 : inf;
        for( int i = 1; i <= N; i++)
        {
            scanf("%d", &M);
            for( int j = 1; j <= M; j++)
            {
               scanf("%d%d", &a, &b);
               mp[i][a] = b;
            }
        }
        Floyd();
        solve( );     
    
      }
      return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/07/12/2587350.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/6318693d8743453aa6287cd330e9d60e.png