测评机： Xeost[5]

得分： 20分

提交日期： 2009-1-15 11:05:00

有效耗时： 204毫秒

测试结果1: 通过本测试点|有效耗时157:ms

测试结果2: 测试结果错误.错误结果为:56342

正确结果应为:42880

测试结果3: 测试结果错误.错误结果为:147526

正确结果应为:139949

测试结果4: 测试结果错误.错误结果为:94550

正确结果应为:83199

测试结果5: 测试结果错误.错误结果为:173818

正确结果应为:165204

测试结果6: 测试结果错误.错误结果为:56342

正确结果应为:42880

测试结果7: 测试结果错误.错误结果为:55558

正确结果应为:37870

测试结果8: 测试结果错误.错误结果为:167705

正确结果应为:159982

测试结果9: 测试结果错误.错误结果为:65014

正确结果应为:50493

测试结果10: 通过本测试点|有效耗时47:ms

提交代码： var

cost:array[1..1000,1..1000]of longint；

m,n,o,p,q,r:longint；

procedure prim；

var

lowcost,closest:array[1..1000]of longint；

i,j,k,min:longint；

begin

for i:=1to m do

begin

lowcost[i]:=cost[1,i]；

closest[i]:=1；

end；

for i:=1to m-1do

begin

min:=2147483647；

for j:=1to m do

if(lowcost[j]<min)and(lowcost[j]<>0)

then begin

min:=lowcost[j]；

k:=j；

end；

lowcost[k]:=0；

for j:=1to m do

if cost[k,j]<lowcost[j]

then begin

lowcost[j]:=cost[k,j]；

closest[j]:=k；

end；

end；

j:=0；

for i:=2to m do

j:=j+cost[closest[i],i]；

write(j)；

end；

begin

readln(m,n)；

for o:=1to m do

for p:=1to m do

cost[o,p]:=2147483647；

for o:=1to n do

begin

readln(p,q,r)；

cost[p,q]:=r；

cost[q,p]:=r；

end；

prim；

end.

20分哪里错了!!!

数据太假了!

居然可以重复读同一条路!

一开始我也是20分。。。

BS下这题的数据。。

首先提醒楼主

做图论找最短路赋初值的时候最好不要赋为maxint，这道题没什么影响

其它的问题我也没看出来。

我最早也是用邻接矩阵来保存的，后来改成链表就过了