題意：在一個(gè)帶全有向圖中找一點(diǎn)使其道其它所有點(diǎn)的最短距離最大的那個(gè)最小。
解法：flyod+枚舉點(diǎn)，沒(méi)覺(jué)著和DP有什么關(guān)系。
#include <stdio.h>
#define N 105
#define INF 1 << 28
int g[N][N], mark[N];
void floyd(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(j == k || i == j) continue;
if(g[i][k] + g[k][j] < g[i][j])
{
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
void dfs(int u, int n)
{
mark[u] = 1;
for(int i = 1; i <= n; i++)
{
if(!mark[i]) dfs(i, n);
}
}
int main()
{
int n, m, a, b, dis;
while(scanf("%d", &n), n)
{
for(int i = 1; i <= n; i++)
{
g[i][i] = mark[i] = 0;
for(int j = i + 1; j <= n; j++)
g[i][j] = g[j][i] = INF;
}
for(int i = 1; i <= n; i++)
{
scanf("%d", &m);
for(int j = 0; j < m; j++)
{
scanf("%d %d", &a, &b);
if(b < g[i][a]) g[i][a] = b;
}
}
dfs(1, n);
bool flag = 0;
for(int i = 1; i <= n; i++)
{
if(!mark[i])
{
flag = 1;
break;
}
}
if(flag)
{
printf("disjoint");
continue;
}
floyd(n);
dis = INF;
for(int i = 1; i <= n && mark; i++)
{
b = -INF;
for(int j = 1; j <= n && mark; j++)
{
if(i == j) continue;
if(g[i][j] > b) b = g[i][j];
}
if(b < dis) a = i, dis = b;
}
printf("%d %d\n", a, dis);
}
return 0;
}