# 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.