状态: Unaccepted
测评机： Xeost[5]
得分： 0分
提交日期： 2010-8-12 20:39:00
有效耗时： 该状态没有记录
测试结果1: 选手程序无输出
测试结果2: 选手程序无输出
测试结果3: 选手程序无输出
测试结果4: 选手程序无输出
测试结果5: 选手程序无输出
测试结果6: 选手程序无输出
测试结果7: 选手程序无输出
测试结果8: 选手程序无输出
测试结果9: 选手程序无输出
测试结果10: 选手程序无输出
const
maxn=1000000;
type
code=record
data,weight:integer;
end;
var
queue:array[1..maxn]of integer;
len:array[1..30000,0..10000]of code;
dist:array[1..30000]of longint;
du:array[1..30000]of integer;
visited:array[1..30000]of boolean;
count,i,j,n,m,head,tail,v,s,a,b,w:longint;
begin
assign(input,'tem.in');
reset(input);
readln(n,m);
for i:=1 to n do
for j:=1 to n do len[i,j].weight:=maxint;
fillchar(du,sizeof(du),0);
for i:=1 to m do
begin
readln(a,b,w);
inc(du[a]);
inc(du[b]);
len[a,du[a]].data:=b;
len[b,du[b]].data:=a;
len[a,du[a]].weight:=w;
len[b,du[b]].weight:=w;
end;
close(input);
s:=1;
//SPFA begin
for i:=1 to n do dist[i]:=maxlongint;
fillchar(visited,sizeof(visited),0);
dist[s]:=0;
visited[s]:=true;
count:=1;
head:=1;tail:=1;queue[1]:=s;
while (count>0) do
begin
v:=queue[head];
for i:=1 to du[v] do
begin
j:=len[v,i].data;
if dist[v]+len[v,i].weight<dist[j] then
begin
dist[j]:=dist[v]+len[v,i].weight;
if visited[j]=false then
begin
visited[j]:=true;
inc(count);
inc(tail);
if tail>maxn then tail:=1;
queue[tail]:=j;
end;
end;
end;
visited[v]:=false;
inc(head);
if head>maxn then head:=1;
dec(count);
end;
//SPFA end;
writeln(dist[n]);
end.