1 条题解
-
1
#include<iostream> #include<vector> #include<cstdio> #include<algorithm> #include<queue> using namespace std; bool inroad[10010],can[10010]; //inroad 表示此点是否可以出现在路径上 can 表示此点是否可以到达终点 int dis[10010]; //dis 表示此点距离起点的距离 vector<int>side[10010]; //正向建边 vector<int>edis[10010]; //反向建边 int main() { int n,m,a,b,s,t; cin>>n>>m; for(int i=1;i<=m;i++) //读入并正反向建边 { cin>>a>>b; side[a].push_back(b); edis[b].push_back(a); } cin>>s>>t; can[t]=1; //终点先设置为 1 queue<int>que; que.push(t); while(!que.empty()) //从终点反向查找② { int now=que.front(); que.pop(); for(int i=edis[now].size()-1;i>=0;i--) { int to=edis[now][i]; if(!can[to]) { que.push(to); can[to]=1; } } } if(!can[s]) //起点无法到达终点就直接结束程序 { cout<<"-1"; return 0; } for(int i=1;i<=n;i++) //判断哪些点是① { if(can[i]) { inroad[i]=1; for(int j=side[i].size()-1;j>=0;j--) //遍历所有的边 { int to=side[i][j]; if(!can[to]) //如果它出边所到达的点无法到达终点,这个点就不可以出现在路径上 { inroad[i]=0; break; } } } } if(!inroad[s]) //这里需要特殊判定一下起点是否满足条件,感谢 @WestTree 的HACK { cout<<"-1"; return 0; } dis[s]=1;que.push(s); while(!que.empty()) //从起点bfs,只经过①点,找出最短距离 { int now=que.front(); que.pop(); if(now==t) //到达终点,输出结果 { cout<<dis[t]-1; return 0; } for(int i=side[now].size()-1;i>=0;i--) { int to=side[now][i]; if(inroad[to]&&!dis[to]) { dis[to]=dis[now]+1; que.push(to); } } } cout<<"-1"; //否则还是无法到达 }
- 1
信息
- ID
- 1248
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者