任务: 求出所给无向图(边权非负)的单源最短路.

输入格式:

第一行: 点数N(2 <= N <= 10,000), 边数M(M <= 100,000), 源点S(1 <= S <= N)

以下M行, 每行三个整数a, b, c表示点a, b(1 <= a, b <= N)之间连有一条边, 权值为c(0 <= c <= 100,000)

Sample Input

6 8 1

1 3 4

1 2 6

3 4 7

6 4 2

2 4 5

3 6 3

4 5 1

3 5 4

Sample Output

0

6

4

9

8

7

输出格式:

N行: 输出源点到各点的最短路, 到该点不连通则输出-1

Program Dijkstra_Mpq;

type link=^node;
     node=record
       Num,Cost:Longint;
       Next:link;
     end;

Const Maxn=100001;
      MaxLong=MaxLongint shr 1;

var
  p:link;
  n,m,start:Longint;
  a:array[0..Maxn] of link;
  x,y,Num:array[1..Maxn] of Longint;

procedure swap(i,j:Longint);
procedure f(var i,j:Longint);
var
  Tmp:Longint;
begin
  Tmp:=i;
  i:=j;
  j:=Tmp;
end;

begin
  f(x[i],x[j]);
  f(y[i],y[j]);
  f(Num[y[i]],Num[y[j]]);
end;

procedure down(r:Longint);
var
  i,j:Longint;
begin
  i:=1; j:=i*2;
  while j<=r do
  begin
    if (x[j]>x[j+1]) and (j<r) then inc(j);
    if x[i]>x[j] then
    begin
      swap(i,j);
      i:=j;
      j:=j shl 1;
    end else exit;
  end;
end;

procedure up(n:Longint);
var
  i,j:Longint;
begin
  j:=n; i:=n shr 1;
  while i>0 do
  begin
    if x[j]<x[i] then
    begin
      swap(i,j);
      j:=i;
      i:=i shr 1;
    end else exit;
  end;
end;

procedure init;
var
  i,xx,yy,zz:Longint;
begin
  fillchar(a,sizeof(a),0);
  readln(n,m,start);
  for i:=1 to m do
  begin
    readln(xx,yy,zz);
    new(a[0]);
    a[0]^.Num:=yy;
    a[0]^.Cost:=zz;
    a[0]^.Next:=a[xx];
    a[xx]:=a[0];
    new(a[0]);
    a[0]^.Num:=xx;
    a[0]^.Cost:=zz;
    a[0]^.Next:=a[yy];
    a[yy]:=a[0];
  end;
  for i:=1 to n do
  begin
    x[i]:=MaxLong;
    y[i]:=i;
    Num[i]:=i;
  end;
  x[start]:=0;
  up(start);
end;

procedure Dijkstra;
var
  i,Len,Tmp:Longint;
begin
  Len:=n;
  for i:=1 to n-1 do
  begin
    swap(1,Len);
    down(Len-1);
    if x[Len]=Maxlong then break;
    p:=a[y[Len]];
    while p<>nil do
    begin
      Tmp:=x[Num[y[Len]]]+p^.Cost;
      if Tmp<x[Num[p^.Num]] then
      begin
        x[Num[p^.Num]]:=Tmp;
        up(Num[p^.Num]);
      end;
      p:=p^.Next;
    end;
    dec(Len);
  end;
  for i:=1 to n do
    if x[Num[i]]=MaxLong then writeln(-1) else
                              writeln(x[Num[i]]);
end;

begin

assign(input,'Dijkstra.in'); reset(input);
assign(output,'Dijkstra.out'); rewrite(output);
  init;
  Dijkstra;
close(input); close(output);
end.