乌托邦有n个城市，某些城市之间有公路连接。任意两个城市都可以通过公路直接或间接到达，并且任意两个城市之间有且仅有一条路径。 每条公路都有自己的长度，这些长度都是已经测量好的。小修想从一个城市出发开车到另一个城市，并且她希望经过的公路总长度最长。请问她应该选择哪两个城市？这个最长的长度是多少？ 【输入文件】wutuo.in 第一行一个整数n(表示n个城市，n≤100)，以下n-1行每行三个整数a,b,c。表示城市之间有公路连接，并且公路的长度是c(c≤10000)。【输出文件】wutuo.out仅一个数，即最长长度【样例数据】 【输入】wutuo.in51 2 22 3 12 4 31 5 4【输出】wutuo.out9
{思路：利用FLOYD算法求出所有结点的最短路径矩阵，
然后求出每个结点到其他的结点的距离总合，取最小的那个}
program capital;
const
maxn=100;
var
n,m,k,i,j:integer;
min,sum:longint;
dist:array[1..maxn,1..maxn] of longint;
{prev:array[1..maxn,1..maxn] of 0..maxn;} {因为无需知道路径，因此略去计算前驱的数组}
procedure init;
var
m,i,u,v:integer;
begin
assign(input,'capital.in');
reset(input);
assign(output,'capital.out');
rewrite(output);
readln(n,m);
{fillchar(prev,sizeof(prev),0);}
for u:=1 to n do
for v:=1 to n do
dist[u,v]:=1000000000;
for i:=1 to m do
begin
readln(u,v,dist[u,v]);
dist[v,u]:=dist[u,v];
{prev[u,v]:=u;
prev[v,u]:=v;}
end;
{readln(s,t);}
end;
procedure floyd;
var
i,j,k:integer;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (dist[i,k]+dist[k,j]<dist[i,j]) then
begin
dist[i,j]:=dist[i,k]+dist[k,j];
{prev[i,j]:=prev[k,j];}
end;
end;{floyd}
{procedure print(i,j:integer); 打印路径过程也不需要
begin
if i=j
then write(i)
else if prev[i,j]=0
then write('No Solution!')
else begin
print(i,prev[i,j]);
write('->',j);
end;
end;}
begin
init;
floyd;
min:=100000000;
for i:=1 to n do
begin
sum:=0;
for j:=1 to n do
if i<>j {自己到自己的路径不能计算在内}
then sum:=sum+dist[i,j];
if min>sum
then begin
min:=sum;
k:=i;
end;
end;
write(k);
close(input);
close(output);
end.
开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明Pascal经典算法 – 乌托邦城市！
