11463:Commandos

問題文
http://uva.onlinejudge.org/external/114/11463.html

ワーシャルフロイドで全点間の最短距離を求めておいて、始点sと始点から最も遠い頂点の距離と、その頂点から終点dまでの距離を求めた。

#include<iostream>
#include<algorithm>
 
#define INF 10000000
 
using namespace std;
 
int V,graph[101][101];
 
void warshall_floyd(void){
  for(int k=0; k<V; k++)
    for(int j=0; j<V; j++)
      for(int i=0; i<V; i++)
    graph[i][j]=min(graph[i][j], graph[i][k]+graph[k][j]);
}
 
int main(void){
 
  int T,m,a,b,s,g;
  cin >> T;
  for(int t=1;t<=T;t++){
    cin >> V >> m;
    fill(graph[0],graph[101],INF);
     
    for(int i=0;i<V;i++)graph[i][i]=0;
     
    for(int i=0;i<m;i++){
      cin >> a >> b;
      graph[a][b]=graph[b][a]=1;
    }
    cin >> s >> g;
    warshall_floyd();
     
    int ans=0;
    for(int i=0;i<V;i++)ans=max(ans,graph[s][i]+graph[i][g]);
    cout << "Case " << t <<": "<<ans<<endl;
  }
  return 0;
}