公司网站怎么规范管理的,做公司网站排名,wordpress cat,个人网站推荐免费【题目链接】
洛谷 P2296 [NOIP2014 提高组] 寻找道路 ybt 1885#xff1a;【14NOIP提高组】寻找道路
【题目考点】
1. 图论#xff1a;广搜
2. 图论#xff1a;反图
【解题思路】
设path数组#xff0c;path[i]表示顶点i出发到终点t是否有路径。 先求path数组#…【题目链接】
洛谷 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];
vectorint g[N], rg[N];//g:正图 rg:反图
void bfs1()
{queueint 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;queueint 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;
}
