最短路径的前提就是i点到k点能够访问。反之就是访问不能。

W.Floyd把j放在外面，i，k放在循环里面。我曾经错误的认为i和k是应该在外层循环，结果造成了长期的心理错觉，以致于一遇见这样的题目就ac不能，进而对Floyd先生产生了强烈的怨念。但是Floyd有证明么？

#include <cstdio>
#include <string>

#define MX 1001

int a[100][100], n, m;

int main()
{
 //freopen("in.txt", "r", stdin);
 while(scanf("%d", &n) && n)
 {
  int i, k, j, ac = 1;
  for(i = 0; i < n; i ++)
  {
   scanf("%d", &m);
   for(k = 0; k < n; k ++)
   {
    a[i][k] = MX;
   }
   for(k = 0; k < m; k ++)
   {
    int ti, tn;
    scanf("%d %d", &ti, &tn);
    a[i][ti - 1] = tn;
   }
  }
  //pa();
  for(j = 0; j < n; j ++)
  {
   for(i = 0; i < n; i ++)
   {
    for(k = 0; k < n; k ++)
    {  
     if(i == k || i == j || j == k) continue;
     if(a[i][j] + a[j][k] < a[i][k])
      a[i][k] = a[i][j] + a[j][k];
    }
   }
  }
  //pa();
  int ans = MX, num;
  for(i = 0; i < n; i ++)
  {
   int mx = 0;
   for(k = 0; k < n; k ++)
   {
    if(i == k) continue;
    if(a[i][k] > mx)
     mx = a[i][k];
   }
   if(mx < ans)
   {
    ans = mx;
    num = i + 1;
   }
  }
  if(ans == MX)
   printf("disjoint\n");
  else
   printf("%d %d\n", num, ans);
 }
 return 0;
}

评论