信息学竞赛图论习题

【输入文件】capital.in

第一行两个整数n,m(n≤100)。下面m行，每行三个整数，第i+1行的整数表示第i条高速公路连接的两个城市编号和长度（0

仅一个数，表示交通中心城市的编号

【样例数据】 【输入】capital.in 5 5 1 2 1 1 5 6 2 3 2 2 4 1 4 5 2

【输出】capital.out 2

{思路：利用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]);

21

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]:=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;

22

end; end; write(k); close(input); close(output); end.

23