type
code=record
num,long:integer;
end;
var
a:array[1..30000,1..500] of code;
i,j,m,n,x,y,z:longint;
dian:array[1..30000] of integer;
procedure spfa;
var
head,tail,i,now:longint;
dui:array[1..10000] of integer;
dist:array[1..30000] of longint;
have:array[1..30000] of boolean;
begin
head:=0; tail:=1;
for i:=1 to n do dist[i]:=maxlongint-1000000;
dui[1]:=1;have[1]:=true; dist[1]:=0;
fillchar(have,sizeof(have),false);
repeat
inc(head);
now:=dui[head];
for i:=1 to dian[now] do
if a[now,i].long+dist[now]<dist[a[now,i].num] then begin
dist[a[now,i].num]:=a[now,i].long+dist[now];
if not have[a[now,i].num] then begin
inc(tail);
dui[tail]:=a[now,i].num;
have[a[now,i].num]:=true;
end;
end;
have[now]:=true;
until head>tail;
writeln(dist[n]);
end;
begin
readln(n,m);
for i:=1 to m do begin
read(x,y,z);
inc(dian[x]);a[x,dian[x]].long:=z; a[x,dian[x]].num:=y;
inc(dian[y]);a[y,dian[y]].long:=z; a[y,dian[y]].num:=x;
end;
spfa;
end.
想这种稀疏图,用BELLMAN比较好,给你一段核心程序:
procedure relax (a,b,d:longint); {松弛操作的过程}
var
x:longint;
begin
x:=di[a]+d;
if x<di [b] then
begin
di[b]:=x;
flag:=false;
end;
end;
{====================main=========================}
di[1]:=0; {初始化}
repeat {进行松弛操作}
flag:=true;
for i:=1 to k do
relax (ipt[i].x,ipt[i].y,ipt[i].di);
until flag;
var
x,y,z:array[1..300000] of longint;
aim :array[1..30000] of longint;
final:array[1..30000] of longint;
d :array[1..30000] of longint;
line :array[1..300000] of longint;
n,m:longint;
procedure quick(l,r:longint);
var
i,j,w,p:longint;
begin
i:=l; j:=r;
w:=x[i+random(j-i+1)];
repeat
while x[i]<w do inc(i);
while w<x[j] do dec(j);
if i<=j then
begin
p:=x[i]; x[i]:=x[j]; x[j]:=p;
p:=y[i]; y[i]:=y[j]; y[j]:=p;
p:=z[i]; z[i]:=z[j]; z[j]:=p;
inc(i); dec(j);
end;
until i>j;
if l<j then quick(l,j);
if i<r then quick(i,r);
end;
procedure init;
var
i:longint;
begin
read(n,m);
for i:=1 to m do
begin
read(x[i],y[i],z[i]);
x[m+i]:=y[i];
y[m+i]:=x[i];
z[m+i]:=z[i];
end;
quick(1,m*2);
aim[x[1]]:=1;
for i:=2 to m*2 do if x[i]<>x[i-1] then
begin
aim[x[i]]:=i;
final[x[i-1]]:=i-1;
end;
end;
procedure SPFA;
var
i,l,r:longint;
begin
fillchar(d,sizeof(d),$7f);
l:=0; r:=1;
line[1]:=1;
d[1]:=0;
while l<r do
begin
inc(l);
for i:=aim[line[l]] to final[line[l]] do
begin
if d[line[l]]+z[i]<d[y[i]] then
begin
d[y[i]]:=d[line[l]]+z[i];
inc(r);
line[r]:=y[i];
end;
end;
end;
write(d[n]);
end;
begin
init;
SPFA;
end.
全过