Description
给定一个包含N个点，M条边的无向图，每条边的边权均为1。 再给定K个三元组(A,B,C)，表示从A点走到B点后不能往C点走(即路径中不能出现连续三个点为ABC)。注意三元组是有序的，如可以从B点走到A点再走到C点。 现在你要在K个三元组的限制下，找出1号点到N号点的最短路径，并输出任意一条合法路径，会有Check检查你的输出。
输入文件第一行有三个数N,M,K，意义如题目所述。 接下来M行每行两个数A,B，表示A,B间有一条边。 再下面K行，每行三个数(A,B,C)描述一个三元组。
Output
输出文件共两行数，第一行一个数S表示最短路径长度。 第二行S+1个数，表示从1到N所经过的节点。
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
【数据范围】
对于40%的数据满足N<=10,M<=20,K<=5。 对于100%的数据满足N<=3000,M<=20000,K<=100000。
题解
第一眼：写spfa有点难啊...
别想啦，这是一个广搜啊啊啊，居然还可以满分，广搜我就不想说了。
代码
var
c,b,s:
array[
0..
100000]
of longint;
f,a:
array[
0..
3000,
0..
3000]
of longint;
k,n,m,min:longint;
procedure main;
var
h,t,i,x:longint;
begin
h:=
0;t:=
1;
while h<=t
do
begin
inc(h);
for i:=
1 to n
do
begin
x:=c[h];
if (a[x,i]=
1)
and(f[c[b[h]],x]<>i)
and(i<>x)
then
begin
inc(t);
c[t]:=i;
s[t]:=s[h]+
1;
b[t]:=h;
if i=n
then
begin
if s[t]<min
then
min:=s[t];
exit;
end;
end;
end;
end;
end;
procedure init;
var
i,x,y,z:longint;
begin
readln(n,m,k);
for i:=
1 to m
do
begin
readln(x,y);
a[x,y]:=
1;
a[y,x]:=
1;
end;
for i:=
1 to k
do
begin
readln(x,y,z);
f[x,y]:=z;
end;
end;
begin
min:=maxlongint;c[
1]:=
1;
init;
main;
writeln(min);
end.
转载请注明原文地址: https://ju.6miu.com/read-1309588.html
