注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

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

go 水墨上仙 2889次浏览 已收录 手机上查看

住在乌托邦首都(编号为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.


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明算法详解之Pascal经典 – 乌托邦交通中心
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……