同PKU2607，腦子不靈活了，太久沒思考問題了。這種當年秒殺的題目還寫了好久。BS自己
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 505
#define INF 1 << 28
int g[N][N], station[N];
bool mk[N];
void Init(int n)
{
memset(mk, 0, sizeof(mk));
for(int i = 1; i <= n; i++)
{
g[i][i] = 0;
for(int j = i + 1; j <= n; j++)
g[i][j] = g[j][i] = INF;
}
}
void Flyod(int n)
{
for(int k = 1; k <= n; k++)
{
for(int i = 1; i <= n; i++)
{
if(i == k) continue;
for(int j = 1; j <= n; j++)
{
if(i == j || j == k) continue;
if(g[i][k] + g[k][j] < g[i][j])
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
int main()
{
// freopen("in", "r", stdin);
int t, f, n;
char data[N];
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &f, &n);
Init(n);
for(int i = 0; i < f; i++)
{
scanf("%d", &station[i]);
mk[station[i]] = 1;
}
gets(data);
while(gets(data))
{
if(!strcmp(data, "")) break;
int a, b, c;
sscanf(data, "%d %d %d", &a, &b, &c);
// printf("%d %d %d\n", a, b, c);
if(c < g[a][b]) g[a][b] = g[b][a] = c;
}
Flyod(n);
int minlength, bestlength, anslength = INF, ans = 1;
for(int i = 1; i <= n; i++)
{
if(mk[i]) continue;
mk[i] = 1;
station[f] = i;
bestlength = -1;
for(int j = 1; j <= n; j++)
{
if(mk[j]) continue;
minlength = INF;
for(int k = 0; k <= f; k++)
{
if(g[j][station[k]] < minlength)
{
minlength = g[j][station[k]];
}
}
if(minlength > bestlength) bestlength = minlength;
}
mk[i] = 0;
if(bestlength < anslength)
{
anslength = bestlength;
ans = i;
}
}
printf("%d\n", ans);
if(t) printf("\n");
}
return 0;
}