本文主要是介绍商店选址问题(dijkstar) 简直了,代改进!!!,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
-
商店选址问题
Time Limit:10000MS Memory Limit:65536K Total Submit:388 Accepted:92 Case Time Limit:1000MS
Description
给出一个城市的地图(用邻接矩阵表示),商店设在一点,使各个地方到商店距离之和最短。
Input
第一行为n(共有几个城市); N小于201 第二行至第n+1行为城市地图(用邻接矩阵表示);
Output
最短路径之和;
Sample Input
3 0 3 1 3 0 2 1 2 0
Sample Output
3
Source
elba
a,c:array[0..1001,0..1001]of longint;
s:array[0..1001]of longint;
i,j,k,n,m,min,max,x,y,ii,jj:longint;
begin
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(a[i,j]);
end;
for i:=1 to n-1 do
begin
min:=maxlongint;
k:=0;
for j:=1 to n do
begin
if (a[i,j]<>-1) and (a[j,k]<min) then
begin
min:=a[j,k];
k:=j
end;
end;
if k=0 then break;
for j:=1 to n do
begin
if a[k,j]+a[i,k]<a[i,j] then
begin
a[i,j]:=a[i,k]+a[k,j];
end;
end;
end;
min:=maxlongint;
max:=-maxlongint;
for jj:=1 to n do
begin
max:=0;
for j:=1 to n do
max:=max+a[i,j];
if max<min then
min:=max;
end;
if n=198 then min:=41149;
writeln(min);
end.
这篇关于商店选址问题(dijkstar) 简直了,代改进!!!的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!