2017811 2006-08-12 20:23:54 Accepted 1082 C++ 00:00.00 428K St.Crux 最短路径的前提就是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;}

评论