Poj Solution 2607

http://poj.org/problem?id=2607

#include <cstdio>
const int M = 505, INF = 1000000000;
int mp[M][M], n, m, f[105];

int main () {
 int i, j, k, x, y, d, u, ans, Max, Min;
 while ( scanf("%d %d", &m, &n) != EOF ) {
  for ( i = 1; i <= m; i++ )
   scanf("%d", f + i);

  for ( i = 1; i <= n; i++ ) {
   for ( j = 1; j <= n; j++ )
    mp[i][j] = INF;
   mp[i][i] = 0;
   }

  while ( scanf("%d %d %d", &x, &y, &d) != EOF ) {
   mp[x][y] = mp[y][x] = d;
   }
//  for ( i = 1; i <= n; i++ ) {
//   for ( j = 1; j <= n; j++ )
//    printf("%d ", mp[i][j]);
//   printf("n");
//   }
//  printf("n");

  for ( k = 1; k <= n; k++ )
   for ( i = 1; i <= n; i++ )
    for ( j = 1; j <= n; j++ )
     if ( mp[i][j] > mp[i][k] + mp[k][j] )
      mp[i][j] = mp[i][k] + mp[k][j];

//  for ( i = 1; i <= n; i++ ) {
//   for ( j = 1; j <= n; j++ )
//    printf("%d ", mp[i][j]);
//   printf("n");
//   }
//  printf("n");

  ans = INF;
  for ( i = 1; i <= n; i++ ) {
   f[m+1] = i;
   Max = 0;
   for ( j = 1; j <= n; j++ ) {
    Min = INF;
    for ( k = 1; k <= m + 1; k++ ) {
     if ( mp[j][ f[k] ] < Min )
      Min = mp[j][ f[k] ];
     }
    if ( Min > Max ) Max = Min;
    }
   if ( Max < ans ) { ans = Max; u = i;}
   }
  printf("%dn", u);
  }
 }
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *