题目描述

给定一个包含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)描述一个三元组。

输出

输出文件共两行数，第一行一个数S表示最短路径长度。
第二行S+1个数，表示从1到N所经过的节点。

思路

bfs。。。。（不知道为什么可以AC）
搜索每个点可以到达的路，并且判断是不是可以走就可以了

pascal

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
  if dep=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;
  while head<=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 begin min:=state[tail];

                 dfs(tail); exit; end;
               end;

    end;
end;

begin
  l:=1;
  readln(n,m,k);
  for i:=1 to m do
    begin
      readln(x,y);
      a[x,y]:=true;
      a[y,x]:=true;
    end;
  for i:=1 to k do
    begin
      readln(x,y,z);
      f[x,y]:=z;
    end;
  bfs;

  writeln(min);
  {for i:=l-1 downto 2 do
    write(xx[i],' ');}
  //writeln(xx[1]);
end.

c++

#include 
#define maxn 3001
#define p 100000
using namespace std;
int t[p],father[p],state[p];
bool a[maxn][maxn];
int f[maxn][maxn];
int i,j,k,m,n,s,x,y,z,min;
int bfs()
{
    int head=0,tail=1,i,j;
    t[1]=1;
    father[1]=0;
    state[1]=0;
    while (head<=tail)
    {
        head++;
        for (i=1;i<=n;i++)
            if (a[t[head]][i]&&f[t[father[head]]][t[head]]!=i&&i!=t[head])
            {
                tail++;
                t[tail]=i;
                state[tail]=state[head]+1;
                father[tail]=head;
                if (i==n)
                {
                    min=state[tail];
                    return 0;
                }
            }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x][y]=true;
        a[y][x]=true;
    }
    for (i=1;i<=k;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        f[x][y]=z;
    }
    bfs();
    printf("%d",min);
    return 0;
}