Description
给定一个包含N个点，M条边的无向图，每条边的边权均为1。 再给定K个三元组(A,B,C)，表示从A点走到B点后不能往C点走(即路径中不能出现连续三个点为ABC)。注意三元组是有序的，如可以从B点走到A点再走到C点。 现在你要在K个三元组的限制下，找出1号点到N号点的最短路径，并输出任意一条合法路径，会有Check检查你的输出。
Input
输入文件第一行有三个数N,M,K，意义如题目所述。 接下来M行每行两个数A,B，表示A,B间有一条边。 再下面K行，每行三个数(A,B,C)描述一个三元组。
Output
输出文件共两行数，第一行一个数S表示最短路径长度。 第二行S+1个数，表示从1到N所经过的节点。
Sample Input
4 4 2 1 2 2 3 3 4 1 3 1 2 3 1 3 4
Sample Output
4 1 3 2 3 4
Hint
【数据范围】 对于40%的数据满足N<=10,M<=20,K<=5。 对于100%的数据满足N<=3000,M<=20000,K<=100000。
因为有那个条件的限制，不好打最短路，直接就上了一个暴力dfs，看看走好还是不走更优
var t,father,state,xx:array[-10..100000] of longint; a:array[0..3001,0..3001]of boolean; f:array[0..3001,0..3001]of longint; i,j,k,n,m,s,x,y,z,min,l:longint; procedure dfs(dep:longint); var i,j,k:longint; begin ifdep=0 then exit; xx[l]:=t[dep]; inc(l); dfs(father[dep]); end; procedure bfs; var head,tail,i,j,k,x,y:longint; begin head:=0; tail:=1; t[1]:=1; father[1]:=0; state[1]:=0; whilehead<=tail do begin inc(head); for i:=1 to n do if (a[t[head],i]) and (f[t[father[head]],t[head]]<>i) and(i<>t[head]) then begin inc(tail); t[tail]:=i; state[tail]:=state[head]+1; father[tail]:=head; if i=n then beginmin:=state[tail]; dfs(tail); exit; end; end; end; end; begin l:=1; readln(n,m,k); fori:=1 to m do begin readln(x,y); a[x,y]:=true; a[y,x]:=true; end; fori:=1 to k do begin readln(x,y,z); f[x,y]:=z; end; bfs; writeln(min); end.
