Hopscotch Addict


给定一个有向图,一次只能走 步,问最少需要几次才能从 走到 .


从 走到 需要的步数一定是 的倍数,用一个 表示从 到 的步数 除 余 ,即 到 有 三种状态,当 存在时,说明从 到 状态为 的最短路径已找到,不必要再找一次.

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
vector<int>g[N];
int dp[N][3];
int n,m,s,t;
int main(){
    //freopen("in.txt","r",stdin);
    me(dp,-1);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        sc("%d%d",&u,&v);
        g[u].push_back(v);
    }
    cin>>s>>t;
    queue<pair<int,int> >q;
    q.push({s,0});
    dp[s][0]=0;
    while(!q.empty()){
        int u=q.front().first;
        int x=q.front().second;
        q.pop();
        for(auto v:g[u]){
            int e=(x+1)%3;
            if(dp[v][e]>=0)continue;
            dp[v][e]=dp[u][x]+1;
            q.push({v,e});
        }
    }
    if(dp[t][0]>=0)dp[t][0]/=3;
    o(dp[t][0]);
}