信息学奥赛一本通 1885：【14NOIP提高组】寻找道路 | 洛谷 P2296 [NOIP2014 提高组] 寻找道路

【题目链接】

洛谷 P2296 [NOIP2014 提高组] 寻找道路
ybt 1885：【14NOIP提高组】寻找道路

【题目考点】

1. 图论：广搜

2. 图论：反图

【解题思路】

设path数组，path[i]表示顶点i出发到终点t是否有路径。
先求path数组，需要对原图建反图，而后从终点t开始进行广搜，广搜过程中访问到的顶点x，表示在反图中从t出发到顶点x有路径，也就是在正图中从顶点x到终点t存在路径。
设sel数组，sel[i]为真表示顶点i可以作为该题要选择的符合条件的路径上的点。
而后遍历所有顶点，对于顶点i，如果i到t有路径，且i的邻接点到t都有路径，那么顶点i可以作为符合条件的路径上的点。
最后从起点s出发进行广搜，求符合条件的路径的最短路径长度。求出从s出发到所有满足sel[i]为真的顶点i的最短路径长度dis[i]。最后dis[t]就是结果。

【题解代码】

解法1：广搜

#include <bits/stdc++.h>
using namespace std;
#define N 10005
bool vis[N], path[N], sel[N];//path[i]:i到t有路径  sel[i]：i以及i的邻接点都到t有路径 
int n, m, s, t, dis[N];
vector<int> g[N], rg[N];//g:正图 rg:反图 
void bfs1()
{queue<int> que;vis[t] = true;que.push(t);while(!que.empty()){int u = que.front();que.pop();path[u] = true;for(int v : rg[u]) if(!vis[v]){vis[v] = true;que.push(v);}}
}
int bfs2()
{if(sel[s] == false)return -1;queue<int> que;vis[s] = true;que.push(s);while(!que.empty()){int u = que.front();que.pop();if(u == t)return dis[u];for(int v : g[u]) if(!vis[v] && sel[v]){vis[v] = true;dis[v] = dis[u]+1; que.push(v);} }return -1;
} 
bool check(int u)
{if(!path[u]) return false;for(int v : g[u]) if(!path[v])return false;return true;
}
int main()
{int x, y;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> x >> y;g[x].push_back(y);rg[y].push_back(x);}cin >> s >> t;bfs1();for(int i = 1; i <= n; ++i)sel[i] = check(i);memset(vis, 0, sizeof(vis));cout << bfs2(); return 0;
}