前言
题意
给你一个有向无权图 , 对于一次移动必须走三个点 , 从 S S S到 T T T需要走最少几次
思路
对于从 S S S走到 T T T,只有三种可能性 , 0 , 1 , 2 0,1,2 0,1,2 ; 因此我们可以使用一个 d i s t [ N ] [ 3 ] dist[N][3] dist[N][3]数组来记录状态,然后我们利用 B F S BFS BFS求一遍最短路即可.最后判断终点状态是否满足条件
CODE
const int N = 1e5+10;
int dist[N][3];
void solve()
{
int n,m;cin>>n>>m;
vector<vector<int>> g(n);
for(int i=1;i<=m;i++){
int a,b;cin>>a>>b;
a--,b-- ;
g[a].pb(b);
}
int S,T;cin>>S>>T;
S -- , T-- ;
memset(dist,0x3f,sizeof dist);
queue<pii> q;
q.push({S,0});
dist[S][0] = 0 ;
while(!q.empty()){
auto t = q.front();
q.pop();
for(auto j : g[t.x]){
int nl = (t.y+1)%3;
if(dist[j][nl]!=0x3f3f3f3f) continue;
dist[j][nl] = dist[t.x][t.y] + 1;
q.push({j,nl});
}
}
int ans = dist[T][0];
if(ans == 0x3f3f3f3f){
cout<<-1<<endl;
return;
}
else ans/=3;
cout<<ans<<endl;
}