用Floyd，可以说是加了dp的思想就可以过了
#define INF  1<<30 
for(k = 1; k <= n; k++) {
        for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++) {
            if(map[i][k] != INF && map[k][j] != INF) {
                map[i][j] = min(max(map[i][k], map[k][j]), map[i][j]);
            }
        }
 }
////////////////////////////////////////////////////////
 for(i = 0; i < t; i++) {
      scanf("%d%d", &x, &y);
      if(map[x][y] != INF) printf("%d\n", map[x][y]);
      else printf("-1\n");
}
这样就OK啦～