【UVa】11463 - Commandos

Problem here

Solution

floyd刷所有點到其他點的最短路
再在上面找開始點到集合點的最大值

#include <iostream>
#include <memory.h>
#define MAX_NUM 1<<29
using namespace std;
int main(){
    int kase;
    cin >> kase;
    int cnt = 1;
    while(kase--){
        int n, r;
        int rat[101][101];
        cin >> n >> r;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(i==j)
                    rat[i][j] = rat[j][i] = 0;
                else
                    rat[i][j] = MAX_NUM;
        int s, e;
        while(r--){
            int x, y;
            cin >> x >> y;
            rat[x][y] = rat[y][x] = 1;
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                for(int k = 0; k < n; k++)
                    if(rat[j][i] + rat[i][k] < rat[j][k])
                        rat[j][k] = rat[j][i] + rat[i][k];
        cin >> s >> e;

        int ans = 0;
        for(int i = 0; i < n; i++)
            if(ans < rat[s][i] + rat[i][e])
                ans = rat[s][i] + rat[i][e];
        cout << "Case " << cnt++ << ": " << ans << endl;
    }
    return 0;
}