首页 > 代码库 > P2296 寻找道路
P2296 寻找道路
P2296 寻找道路
题目描述
在有向图G 中，每条边的长度均为1 ，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1 ．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2 ．在满足条件1 的情况下使路径最短。
注意：图G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入输出格式
输入格式：
输入文件名为road .in。
第一行有两个用一个空格隔开的整数n 和m ，表示图有n 个点和m 条边。
接下来的m 行每行2 个整数x 、y ，之间用一个空格隔开，表示有一条边从点x 指向点y 。
最后一行有两个用一个空格隔开的整数s 、t ，表示起点为s ，终点为t 。
输出格式：
输出文件名为road .out 。
输出只有一行，包含一个整数，表示满足题目?述的最短路径的长度。如果这样的路径不存在，输出- 1 。
输入输出样例
3 2 1 2 2 1 1 3
-1
6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5
3
说明
解释1：
如上图所示，箭头表示有向道路，圆点表示城市。起点1 与终点3 不连通，所以满足题
目?述的路径不存在，故输出- 1 。
解释2：
如上图所示，满足条件的路径为1 - >3- >4- >5。注意点2 不能在答案路径中，因为点2连了一条边到点6 ，而点6 不与终点5 连通。
对于30%的数据，0<n≤10，0<m≤20；
对于60%的数据，0<n≤100，0<m≤2000；
对于100%的数据，0<n≤10,000，0<m≤200,000，0<x，y，s，t≤n，x≠t。
因为有些点是不能用的，所以首先可以搜索出这些点并排除这些点，要所有的点都指向终点且不能在指向其他的，可以在建边时反向建边，从终点dfs，找出每个点访问的次数，在记录一下他的出度，如果这两个值相等，则说明指向的只有终点，这个点也就可以用，然后bfs找最短路径，首先找到的就是最短的，所有的边权都是1，只需记录步数即可
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 using namespace std; 5 const int MAXN = 10100; 6 struct Edge{ 7 int to,nxt; 8 }e[200100]; 9 struct node{10 int step,x;11 }cur,nxt;12 int chu[MAXN],cnt[MAXN],head[MAXN];13 bool vis[MAXN];14 int n,m,s,t,tot;15 queue<node>q;16 17 void add(int a,int b)18 {19 e[++tot].nxt = head[a];20 e[tot].to = b;21 head[a] = tot;22 chu[b]++;23 }24 void dfs(int x)25 {26 if (cnt[x]++) return ;27 for (int i=head[x]; i; i=e[i].nxt)28 dfs(e[i].to);29 }30 void bfs()31 {32 cur.x = t,cur.step = 0;33 q.push(cur);34 vis[t] = true ;35 while (!q.empty())36 {37 cur = q.front();38 q.pop();39 for (int i=head[cur.x]; i; i=e[i].nxt)40 {41 int v = e[i].to;42 if (!vis[v]&&cnt[v]==chu[v])43 {44 if (v==s)45 {46 printf("%d",cur.step+1);47 return ;48 }49 vis[v] = true;50 nxt.x = v; nxt.step = cur.step+1;51 q.push(nxt);52 }53 }54 }55 printf("-1"); 56 }57 int main()58 {59 scanf("%d%d",&n,&m);60 for (int a,b,i=1; i<=m; ++i)61 {62 scanf("%d%d",&a,&b);63 add(b,a);64 }65 scanf("%d%d",&s,&t);66 dfs(t);67 bfs();68 return 0;69 }
P2296 寻找道路