算法详解之Pascal经典 – 乌托邦交通中心

住在乌托邦首都（编号为1）的天凯，开始对首都的交通情况感到不满，因为，他发现首都到某些城市，即使他选择最短的路径，距离也非常远。因此他想让你求一下交通中心城市是哪座城市（也有可能就是首都）。 为了说明交通中心城市的概念，先定义G[i]为距离城市i最远的城市（到城市i的最短路径长度最长的城市）到城市i的距离。那么交通中心城市都是G[i]最小的城市，如果有几个城市的G[i]一样小，则是编号最小的那个。【输入文件】capital.in 第一行两个整数n,m(n≤100)。下面m行，每行三个整数，第i+1行的整数表示第i条高速公路连接的两个城市编号和长度（0<L<10000）。【输出文件】capital.out仅一个数，表示交通中心城市的编号【样例数据】 【输入】capital.in5 51 2 11 5 62 3 22 4 14 5 2【输出】capital.out2

{思路：利用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.