gym 101987 J Starwars(bfs)

题意

给定一张1e3的有向图，每条路径都有一个编码 （编码范围为20），并给出一些人类点，和目的点，求是否存在从非人类点出发到目的点的路径编号序与人类店出发到目标点的路径编码序一样。存在输出YES，否则NO

题解

倒着去考虑，假若存在一条一样的路那么从后往前回溯路径发现两条路径的起点都为目标点，终点一个为人类点，一个为非人类点，之后我们考虑两个状态代表人类和非人类，他们的出发点都为目标点，之后他们两两选择的路径需要保证路径编号一样，因此我们只要将所有可行的出发点塞入队列，跑bfs，最后check是否存在一个非人类点和一个人类点这样的状态是可达状态，若存在则YES，否则NO

代码

/**
 *     author:     TelmaZzzz
 *     create:     2019-10-02-21.46.23
**/
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
//#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
void _R(int &x) { scanf("%d", &x); }
void _R(ll &x) { scanf("%lld", &x); }
void _R(db &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
void _W(const int &x) { printf("%d", x); }
void _W(const ll &x) { printf("%lld", x); }
void _W(const db &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define erp(x,y,z) for(int x=y;x>=z;x--)
#define PB push_back
#define MP make_pair
#define INF 1073741824
#define inf 1152921504606846976
#define pi 3.14159265358979323846
#define Fi first
#define Se second
//#pragma comment(linker,"/STACK:10240000,10240000")
//mt19937 rand_(time(0));
const int N=1200,M=2e6;
const long long mod=1e9+7;
inline int read(){int ret=0;char ch=getchar();bool f=1;for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');for(;isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;return f?ret:-ret;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}//逆元
//int head[N],NEXT[M],ver[M],tot;void link(int u,int v){ver[++tot]=v;NEXT[tot]=head[u];head[u]=tot;}
void TelmaZzzz(){
#ifndef ONLINE_JUDGE
    freopen("1.txt","r",stdin);
#endif
}
 
vector<pair<int,int> >E[N];
queue<pair<int,int> >q;
bool vis[N][N];
bool hm[N];
int ml[N];
int main(){
    TelmaZzzz();
    //ios::sync_with_stdio(false);
    int n,w,c,h,m;
    int u,v,val;
    R(n,w,c,h,m);
    int inp;
    rep(i,1,h){
        R(inp);
        hm[inp]=true;
        //R(hm[i]);
    }
    rep(i,1,m){
        R(ml[i]);
    }
    rep(i,1,w){
        R(u,val,v);
        E[v].PB(MP(u,val));
    }
    rep(i,1,m){
        rep(j,1,m){
            q.push(MP(ml[i],ml[j]));
            vis[ml[i]][ml[j]]=true;
        }
    }
    while(q.size()){
        pair<int,int> now=q.front();
        q.pop();
        //cout<<now.Fi<<' '<<now.Se<<endl;
        for(auto &x:E[now.Fi]){
            for(auto &y:E[now.Se]){
                //cout<<x.Fi<<' '<<y.Fi<<endl;
                if(vis[x.Fi][y.Fi]) continue;
                if(x.Se==y.Se){
                    vis[x.Fi][y.Fi]=true;
                    q.push(MP(x.Fi,y.Fi));
                }
            }
        }
    }
    rep(i,0,n-1){
        if(!hm[i]) continue;
        rep(j,0,n-1){
            if(!hm[j]){
                if(vis[i][j]){
                    puts("YES");
                    return 0;
                }
            }
        }
    }
    puts("NO");
    return 0;
    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}