O（n^2）Dijkstra求单源最短路，把所有的顶点分为已找到最短路（s）和没有找到最短路（t）的两个集合，将顶点依次加入s中，对新加入的点进行松弛。d[u]+a[u,i]<d[i]var d:array[1..7000] of longint; a:array[1..3000,1..3000] of longint; mark:array[1..7000] of boolean; n,b,c,e:longint;PRocedure dij(v0:integer);var i,j,u,min:integer;begin fillchar(mark,sizeof(mark),false); mark[v0]:=true; for i:=1 to n do d[i]:=a[v0,i]; repeat u:=0;min:=maxint; for i:=1 to n do if (not mark[i])and(d[i]<min) then begin u:=i; min:=d[i]; end; if u<>0 then begin mark[u]:=true; for i:=1 to n do if (not mark[i])and(d[u]+a[u,i]<d[i])then begin d[i]:=d[u]+a[u,i]; end; end; until u=0;end;procedure init;var i,x,y,z:longint;begin readln(n,b,c,e); for i:=1 to b do begin readln(x,y,z); a[x,y]:=z; a[y,x]:=z; end;end;begin fillchar(a,sizeof(a),$7f); init; dij(c); writeln(d[e]);end.
