POJ. 2139 Six Degrees of Cowvin Bacon

1.Problem
http://poj.org/problem?id=2139

2.Idea
Calculate all distance between 2 nodes by Warshall-Floyd.

3.Source:

 
 int n, m;  
 int d[333][333];  
 void solve()  
 {  
      //fill(d, d + 333 * 333, INF);  
      for (int k = 0; k < n; k++)  
           for (int i = 0; i < n; i++)  
                for (int j = 0; j < n; j++) {  
                     d[i][j] = min(d[i][j], d[i][k] + d[k][j]);  
                }  
      int ans = INF;  
      for (int i = 0; i < n; i++) {  
           int sum = 0;  
           for (int j = 0; j < n; j++) {  
                sum += d[i][j];  
           }  
           ans = min(ans, sum * 100 / (n - 1));  
      }  
      cout << ans << endl;  
 }  
 int main()  
 {  
      cin >> n >> m;  
      for (int i = 0; i < n; i++)  
           for (int j = 0; j < n; j++) {  
                if (i == j) d[i][j] = 0;  
                else d[i][j] = INF;  
           }  
      for (int i = 0; i < m; i++) {  
           int k;  
           cin >> k;  
           int x[333];  
           for (int j = 0; j < k; j++) {  
                cin >> x[j];  
                x[j]--;  
           }  
           for (int i = 0; i < k; i++)   
                for (int j = i + 1; j < k; j++) {  
                     d[x[i]][x[j]] = d[x[j]][x[i]] = 1;  
                }  
      }  
      solve();  
      return 0;  
 }