UC知道信息学问题 给出解答者重赏
来源：百度知道 编辑：UC知道 时间：2024/06/21 06:10:57
居民区规划（city.pas）
浦东新区准备开发一片荒地，目前已经规划好了一些居民点，还要建些道路。由于经费问题，他们想在 任意两点间距离最短 的前提下，用尽可能少的投资把各个点连接起来。需要注意的是并不是任意两个居民点都能直接连接。给出两两居民点间建路的花费（与距离成正比），你能帮政府选择一个最佳方案吗？
输入格式：第一行是一个整数N（N<100），表示N个居民点。以下N行每行N个数，第i行第j个数表示居民点i到居民点j的建路费用Wij（0<Wij<10000，Wij=Wji），非正整数表示两地不可直连。输入数据保证有解。
输出格式：第一行输出总花费。然后输出N行，每行N个数，第i行第j个数表示居民点i到居民点j的路，用1表示选取这条路，0则不选。
输入输出样例：
City.in
3
0 2 1
2 0 3
1 3 0
City.out
3
0 1 1
1 0 0
1 0 0
（看清楚了，要在 任意两点间距离最短 的前提下）
速求神牛解答，谢谢
浦东新区准备开发一片荒地，目前已经规划好了一些居民点，还要建些道路。由于经费问题，他们想在 任意两点间距离最短 的前提下，用尽可能少的投资把各个点连接起来。需要注意的是并不是任意两个居民点都能直接连接。给出两两居民点间建路的花费（与距离成正比），你能帮政府选择一个最佳方案吗？
输入格式：第一行是一个整数N（N<100），表示N个居民点。以下N行每行N个数，第i行第j个数表示居民点i到居民点j的建路费用Wij（0<Wij<10000，Wij=Wji），非正整数表示两地不可直连。输入数据保证有解。
输出格式：第一行输出总花费。然后输出N行，每行N个数，第i行第j个数表示居民点i到居民点j的路，用1表示选取这条路，0则不选。
输入输出样例：
City.in
3
0 2 1
2 0 3
1 3 0
City.out
3
0 1 1
1 0 0
1 0 0
（看清楚了，要在 任意两点间距离最短 的前提下）
速求神牛解答，谢谢
program city;
const maxn=100;
var a,d,f:array[1..maxn,1..maxn] of longint;
i,j,k,n:longint;
ans:longint;
begin
assign(input,'city.in');
reset(input);
assign(output,'city.out');
rewrite(output);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(a[i,j]);
f[i,j]:=1;
if a[i,j]<0 then
begin
a[i,j]:=maxint;
f[i,j]:=0;
f[j,i]:=0;
end;
if i=j then
begin
a[i,j]:=maxint;
f[i,j]:=0;
end;
end;
d:=a;
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do
if d[i,j]>=d[i,k]+d[j,k] then
begin
d[i,j]:=d[i,k]+d[j,k];
f[i,j]:=0;
f[j,i]:=0;