【题目链接】
洛谷 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;
}