数组的范围改了n遍...终于过了...

可是最后一个点的时间....

状态题目:星门跳跃

题目编号:341-星门跳跃 查看该题

状态: Accepted

测评机： Xeost[5]

得分： 100分

提交日期： 2009-10-28 17:48:00

有效耗时： 3455毫秒

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

测试结果2: 通过本测试点|有效耗时156ms

测试结果3: 通过本测试点|有效耗时172ms

测试结果4: 通过本测试点|有效耗时203ms

测试结果5: 通过本测试点|有效耗时235ms

测试结果6: 通过本测试点|有效耗时360ms

测试结果7: 通过本测试点|有效耗时297ms

测试结果8: 通过本测试点|有效耗时250ms

测试结果9: 通过本测试点|有效耗时578ms

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

....

好悬啊...

program Rq341；

var

i,j,k,m,n,a,b,c,now,l,r:longint；

map:array[1..80000,0..90]of integer；

quan:array[1..80000,0..90]of longint；

d:array[1..80000]of integer；

v:array[1..80000]of boolean；

dist:array[1..80000]of longint；

procedure SPFA；

var

i:integer；

begin

while l<=r do

begin

now:=d[l]；

for i:=1 to map[now,0] do

begin

if dist[map[now,i]]>dist[now]+quan[now,i] then

begin

dist[map[now,i]]:=dist[now]+quan[now,i]；

if not v[map[now,i]] then

begin

inc(r)；

d[r]:=map[now,i]；

v[map[now,i]]:=true；

end；

end；

end；

v[now]:=false；

inc(l)；

end；

end；

begin

l:=1； r:=1；

readln(n,m)；

for i:=1 to n do map[i,0]:=0；

for i:=1 to n do v[i]:=false；

for i:=1 to n do dist[i]:=maxlongint；

d[1]:=1； v[1]:=true； dist[1]:=0；

for i:=1 to m do

begin

readln(a,b,c)；

inc(map[a,0])；

map[a,map[a,0]]:=b；

quan[a,map[a,0]]:=c；

inc(map[b,0])；

map[b,map[b,0]]:=a；

quan[b,map[b,0]]:=c；

end；

SPFA；

writeln(dist[n])；

end.