题意:给你n个路口,每个点可以指向k个路口,其中第一个是指向的初始方向,问从A到B,至少要改变多少个路口的方向,如果不能到达B输出-1。
思路:对于每个路口,我们可以用数组来记录初始方向。我们再把整个路口和可以指向的方向看作一张图,从A点开始深搜,一直到找到B点位置,在这个过程中要记录在某个路口走的方向和这个路口初始方向不一样的个数,然后取最小的。
#include<iostream> #include<cstdio> #include<cstring> #define maxn 1<<29 using namespace std; int fst[105],next[10005],node[10005],en; int n,s,t,x[105],k,ans; bool vis[105]; void add(int u,int v) { next[++en]=fst[u]; fst[u]=en; node[en]=v; } void dfs(int u,int num) { if(num>=ans)return; vis[u]=1; if(u==t) { if(num<ans)ans=num; vis[u]=0; return; } for(int i=fst[u];i!=-1;i=next[i]) { int v=node[i]; if(!vis[v]) { if(v==x[u])dfs(v,num); else dfs(v,num+1); } } vis[u]=0; } int main() { int u; en=0; scanf("%d%d%d",&n,&s,&t); memset(fst,-1,sizeof(fst)); memset(x,0,sizeof(x)); for(int i=1;i<=n;i++) { scanf("%d",&k); scanf("%d",&u); add(i,u); x[i]=u; for(int j=1;j<k;j++) { scanf("%d",&u); add(i,u); } } ans=maxn; memset(vis,0,sizeof(vis)); dfs(s,0); if(ans==maxn)cout<<-1<<endl; else cout<<ans<<endl; return 0; }