记录编号	39421	评测结果	AAAAAAAAAA
题目名称	三元限制最短路	最终得分	100
用户昵称	isabella	是否通过	通过
代码语言	Pascal	运行时间	0.283 s
提交时间	2012-07-10 17:02:13	内存使用	73.72 MiB

type
 point=^node;
 node=record
  x,y,c:longint;
  next:point;
  end;
var
 map,d,fa,forbid:array[1..2000,0..2000]of longint;
 f:array[1..3000,1..3000]of boolean;
 a:array[1..3010]of longint;
 rec:array[1..20000]of longint;
 v:array[1..3010]of boolean;
 ha:array[-1..1000000]of point;
 n,m,k,i,j,x,y,head,tail,ff,ans,tot,temp:longint;

 procedure inputhash(a,b,d:longint);
  var temp,t:longint;p:point;
  begin
   t:=(b mod 10)+1;
   temp:=(a+n*b-b)*a;
   temp:=temp mod 999991 +1;
   new(p);
   p^.x:=a;p^.y:=b;p^.c:=d;p^.next:=ha[temp];ha[temp]:=p;
  end;

 function findhash(a,b:longint):longint;
  var temp,t:longint;p:point;
  begin
   t:=(b mod 10)+1;
   temp:=(a+n*b-b)*a;
   temp:=temp mod 999991 +1;

   p:=ha[temp];
   while p<>nil do
    begin
     if (p^.x=x)and(p^.y=y)then exit(p^.c);
     p:=p^.next;
    end;
  end;

begin
assign(input,'patha.in');reset(input);
assign(output,'patha.out');rewrite(output);
{init}
 {inputhash(1,2,3);
 temp:=findhash(1,3); writeln(temp);
 halt; }

 fillchar(f,sizeof(f),0);
 readln(n,m,k);
 for i:=1 to m do
  begin
   read(x,y);
   if f[x,y]=false then begin
      inc(map[x,0]);map[x,map[x,0]]:=y;
      inc(map[y,0]);map[y,map[y,0]]:=x;
      f[x,y]:=true;f[y,x]:=true;
      end;
  end;
 //for i:=1 to k do begin read(x,y,j);inputhash(x,y,j);end;
 for i:=1 to k do read(x,y,forbid[x,y]);

{spfa}
 fillchar(v,sizeof(v),0);
 fillchar(d,sizeof(d),$7f);
 for i:=1 to n do d[i,1]:=0;
 head:=0;tail:=0;
 v[1]:=true;
 for i:=1 to map[1,0]do
  begin
   j:=map[1,i];
   fa[j,0]:=1;fa[j,1]:=1;d[1,j]:=1;
   inc(tail);a[tail]:=j;v[j]:=true;
  end;

 repeat
  head:=(head mod n)+1;
  x:=a[head];
  for j:=1 to fa[x,0]do
   begin
    ff:=fa[x,j];
    temp:=forbid[ff,x];
    for i:=1 to map[x,0] do
     if (temp<>map[x,i])and(d[ff,x]+1<d[x,map[x,i]]) then
        begin
         if d[x,map[x,i]]>2000000000 then
           begin inc(fa[map[x,i],0]);fa[map[x,i],fa[map[x,i],0]]:=x;end;
         d[x,map[x,i]]:=d[ff,x]+1;
         if v[map[x,i]]=false then begin
                                    v[map[x,i]]:=true;
                                    tail:=(tail mod n)+1;
                                    a[tail]:=map[x,i];
                                   end;
        end;
   end;
  v[x]:=false;
 until head=tail;

 ans:=maxlongint;
 for i:=1 to n do
  if d[i,n]<ans then
   begin ans:=d[i,n];ff:=i;end;

 writeln(ans);

 i:=n;tot:=2;
 rec[1]:=n;rec[2]:=ff;
 while ff<>1 do
  begin
   ans:=ans-1;
   i:=ff;
   for j:=1 to n do
    if d[j,i]=ans then
     begin ff:=j;break;end;
   inc(tot);rec[tot]:=ff;
  end;
 for i:=tot downto 1 do write(rec[i],' ');writeln;

close(input);close(output);
end.