状压dp，松鼠从起点出发，拿到所有坚果，然后返回起点，求最短时间。

UVA10944

松鼠从起点出发，拿到所有坚果，然后返回起点，求最短时间。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cstring>

 #include<map>

 #include<set>

 #include<cmath>

 #include<queue>

 #include<bitset>

 #include<utility>

 #include<functional>

 #include<iomanip>

 #include<sstream>

 #include<ctime>

 #include<cassert>

 #define A first

 #define B second

 #define mp make_pair

 #define pb push_back

 #define pw(x) (1ll << (x))

 #define sz(x) ((int)(x).size())

 #define all(x) (x).begin(),(x).end()

 #define rep(i,l,r) for(int i=(l);i<(r);i++)

 #define per(i,r,l) for(int i=(r);i>=(l);i--)

 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)

 #define eps 1e-9

 #define PIE acos(-1)

 #define cl(a,b) memset(a,b,sizeof(a))

 #define fastio ios::sync_with_stdio(false);cin.tie(0);

 #define lson l , mid , ls

 #define rson mid + 1 , r , rs

 #define ls (rt<<1)

 #define rs (ls|1)

 #define INF 0x3f3f3f3f

 #define lowbit(x) (x&(-x))

 #define sqr(a) a*a

 #define ll long long

 #define ull unsigned long long

 #define vi vector<int>

 #define pii pair<int, int>

 #define dd(x) cout << #x << " = " << (x) << ", "

 #define de(x) cout << #x << " = " << (x) << "\n"

 #define endl "\n"

 using namespace std;

 //**********************************

 int n,m;

 map<string,int>ids;

 const int maxn=;

 //**********************************

 inline int id(string s)

 {

     if(ids.count(s))return ids[s];

     return ids[s]=sz(ids);

 }

 int f[maxn][maxn];

 //**********************************

 int main()

 {

     string a,c,d,e,b;

     cin>>n>>m;

     FOR(i,,n){

         cin>>a>>c>>d>>e>>b;

         f[id(a)][id(b)]=;

     }

     int g=sz(ids);

     FOR(k,,g)FOR(i,,g)FOR(j,,g)f[i][j]=f[i][j]||(f[i][k]&&f[k][j]);

     FOR(i,,m){

         cin>>a>>c>>d>>e>>b;

 //        cout<<a<<c<<d<<e<<b<<endl;

 //        de(!ids.count(a)||!ids.count(b));

 //        de(f[id(a)][id(b)]);

         if(!ids.count(a)||!ids.count(b))cout<<"Pants on Fire"<<endl;

         else if(f[id(a)][id(b)])cout<<"Fact"<<endl;

         else if(f[id(b)][id(a)])cout<<"Alternative Fact"<<endl;

         else cout<<"Pants on Fire"<<endl;

     }

     return ;

 }