记录编号	26008	评测结果	AAAAAAAAAAAAAAAAA
题目名称	网络探测	最终得分	100
用户昵称	reamb	是否通过	通过
代码语言	Pascal	运行时间	0.864 s
提交时间	2011-07-22 15:57:43	内存使用	42.13 MiB

program wangluozhentan;
var
  dist:array[0..1000,0..10]of longint;
  map:array[0..1000,0..1000]of longint;
  bz:array[0..1000]of boolean;
  team:array[1..10000000]of longint;
  i,x,y,z,n,m,tt,min:longint;
procedure spfa;
var
  t,w,k,d,l:longint;
begin
  for k:=0 to n do
    for l:=0 to 10 do
    begin
      dist[k,l]:=maxlongint;
      bz[k]:=true
    end;
  dist[0,0]:=0;
  team[1]:=0;
  bz[0]:=false;
  t:=1;
  w:=1;
  while t<=w do
  begin
    d:=team[t];
    inc(t);
    bz[d]:=true;
    for l:=0 to 9 do
      if (dist[d,l]<>maxlongint) then
      for k:=1 to n do
      if (map[d,k]<>0)and(dist[d,l]+map[d,k]<dist[k,l+1]) then
      begin
        dist[k,l+1]:=dist[d,l]+map[d,k];
        if bz[k] then
        begin
          inc(w);
          team[w]:=k;
          bz[k]:=false
        end
      end
  end
end;
begin
  assign (input,'ping.in');
  reset (input);
  assign (output,'ping.out');
  rewrite (output);
    readln (n,m,tt);
    for i:=1 to m do
    begin
      readln (x,y,z);
      if map[x,y]=0 then
      begin
        map[x,y]:=z;
        map[y,x]:=z;
      end
      else
        if z<map[x,y] then
        begin
          map[x,y]:=z;
          map[y,x]:=z;
        end;
    end;
    spfa;
    min:=maxlongint;
    for i:=0 to 10 do
      if (dist[tt,i]<>0)and(dist[tt,i]<min) then
        min:=dist[tt,i];
    if tt=0 then
      min:=0;
    if min<>maxlongint then
      writeln(min)
    else
      writeln('no');
  close (input);
  close (output)
end.