记录编号	39439	评测结果	AAAAAAAAAA
题目名称	三元限制最短路	最终得分	100
用户昵称	czp	是否通过	通过
代码语言	Pascal	运行时间	0.119 s
提交时间	2012-07-11 16:07:20	内存使用	72.67 MiB

type px=^py;
py=record
 d1,d2,d3:longint;
 n:px;
 end;
var
 lx,ly,pre:array[0..2000000] of longint;
 d:array[1..3000,0..3000]of longint;
 a:array[1..3000,0..1000] of longint;
 hash:array[0..1000006] of px;
 i,j,m,n,x,y,u,k,h,t,z:longint;
 bbbb:boolean;
procedure insert(x,y,z:int64);
var date:int64;   pv:px;
begin
  date:=(((x+371)mod 1000007 *(y+123))mod 1000007*(z+277)) mod 1000007;
  pv:=hash[date];
  while pv<>nil do
   begin
    if (pv^.d1=x)
    and(pv^.d2=y)and(pv^.d3=z) then
    break;
    pv:=pv^.n;
   end;
  if pv=nil then
   begin
    new(pv);
    pv^.d1:=x;
    pv^.d2:=y;
    pv^.d3:=z;
    pv^.n:=hash[date];
    hash[date]:=pv;
   end;
end;
function find(x,y,z:int64):boolean;
var date:int64;   pv:px;
begin
  date:=(((x+371)mod 1000007 *(y+123))mod 1000007*(z+277)) mod 1000007;
  pv:=hash[date];
  while pv<>nil do
   begin
    if (pv^.d1=x)
    and(pv^.d2=y)and(pv^.d3=z) then
    break;
    pv:=pv^.n;
   end;
  if pv<>nil then find:=true else find:=false;
end;
procedure print(v:longint);
begin
 if pre[v]<>0 then print(pre[v]);
 writeln(ly[v]);
end;
begin
 assign(input,'patha.in');reset(input);
 assign(output,'patha.out');rewrite(output);
 readln(n,m,k);
 for i:=1 to m do
  begin
   readln(x,y);
   inc(a[x,0]);
   a[x,a[x,0]]:=y;
   inc(a[y,0]);
   a[y,a[y,0]]:=x;
  end;
 for i:=1 to k do
  begin
   readln(x,y,z);
   insert(x,y,z);
  end;
 for i:=1 to n do d[i,1]:=1;
 h:=0;t:=1;
 lx[1]:=1;ly[1]:=1;
 repeat
  inc(h);
  i:=lx[h];j:=ly[h];
  for u:=1 to a[j,0] do
   begin
    bbbb:=find(i,j,a[j,u]);
    if (not bbbb) and (d[j,a[j,u]]=0) then
     begin
      d[j,a[j,u]]:=d[i,j]+1;
      inc(t);
      pre[t]:=h;
      lx[t]:=j;ly[t]:=a[j,u];
      if a[j,u]=n then
       begin writeln(d[i,j]); print(t); close(input);close(output);halt; end;
     end;
   end;
 until h>=t;
 close(input);close(output);
end.