(UVA) 10805 - Cockroach Escape Networks

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1746

主要的想法是說：先做一次all-pair shortest path，得知每個點與每個點的距離，之後對於每個點，抓離這兩個點最遠距離加起來的最小值，理論上就是答案。

但是，試試看這筆測資：

6 5
0 1
0 2
0 3
3 4
3 5

答案應該是3，不是4！

怎麼會這樣？

原來，在 "邊的中間" 的點，也有可能是選項喔！

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 505;
const int INF = 1e9+7;

int dp[MAX_N][MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    for (int qq=1;T>=qq;qq++) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=1;MAX_N>x;x++) {
            for (int y=1;MAX_N>y;y++) {
                dp[x][y] = INF;
                if (x==y) dp[x][y] = 0;
            }
        }
        int id=n+1;
        for (int x=1;m>=x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            i++;
            j++;
            dp[i][id] = dp[id][i] = 1;
            dp[j][id] = dp[id][j] = 1;
            id++;
        }
        int tmpn=n;
        n = id-1;
        for (int k=1;n>=k;k++) {
            for (int i=1;n>=i;i++) {
                for (int j=1;n>=j;j++) {
                    dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j]);
//                    cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
                }
            }
        }
        int ans = INF;
        for (int i=1;n>=i;i++) {
            sort(dp[i]+1,dp[i]+tmpn+1);
            ans = min(ans , dp[i][tmpn]+dp[i][tmpn-1]);
        }
        printf("Case #%d:\n",qq);
        printf("%d\n",ans/2);
        puts("");
    }
}