简答题
偏难
#23481
寻找道路 【问题描述】 在有向图 G 中,每条边的长度均为 1,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件: 1.路径上的所有点的…
寻找道路
【问题描述】
在有向图 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。
【输入输出样例 1】

【输入输出样例说明】

如上图所示,箭头表示有向道路,圆点表示城市。起点 1 与终点 3 不连通,所以满足题目描述的路径不存在,故输出-1。
【输入输出样例 2】

【输入输出样例说明】

如上图所示,满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中,因为点 2连了一条边到点 6,而点 6 不与终点 5 连通。
【数据说明】

答案与解析
正确答案:<p style="text-align: left;">#include<bits/stdc++.h></p><p><br style="text-align: left;"/></p><p style="text-align: left;">#define ll long long</p><p style="text-align: left;">#define MAXN 500010</p><p style="text-align: left;">#define N 201</p><p style="text-align: left;">#define INF 0x7f7f7f7f</p><p style="text-align: left;">#define gtc() getchar()</p><p><br style="text-align: left;"/></p><p style="text-align: left;">using namespace std;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">template <class T></p><p style="text-align: left;">inline void read(T &s){</p><p style="text-align: left;"><span style="white-space:pre"> </span>s = 0; T w = 1, ch = gtc();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!isdigit(ch)){if(ch == '-') w = -1; ch = gtc();}</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(isdigit(ch)){s = s * 10 + ch - '0'; ch = gtc();}</p><p style="text-align: left;"><span style="white-space:pre"> </span>s *= w;</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">template <class T></p><p style="text-align: left;">inline void write(T x){</p><p style="text-align: left;"> if(x < 0) putchar('-'), x = -x;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x > 9) write(x/10);</p><p style="text-align: left;"> putchar(x % 10 + '0');</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">struct node{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y, ne, z;</p><p style="text-align: left;">}e[MAXN];</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int lin[MAXN], len = 0;</p><p style="text-align: left;">inline void add(int x, int y, int z){</p><p style="text-align: left;"><span style="white-space:pre"> </span>e[++len].y = y, e[len].ne = lin[x], lin[x] = len;</p><p style="text-align: left;"><span style="white-space:pre"> </span>e[len].z = z;</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int n, m;</p><p style="text-align: left;">int st, ed;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int col[MAXN], vis[MAXN];</p><p><br style="text-align: left;"/></p><p style="text-align: left;">void bfs(int u){</p><p style="text-align: left;"><span style="white-space:pre"> </span>queue<int> q;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[u] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!q.empty()){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x = q.front(); q.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = lin[x]; i; i = e[i].ne){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y = e[i].y; </p><p style="text-align: left;"><span style="white-space:pre"> </span>if(e[i].z == 1) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(vis[y]) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[y] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">void bfs2(int u){//这个不是bfs,之前写错写成bfs,后来直接在这个函数里改了。</p><p style="text-align: left;"><span style="white-space:pre"> </span>col[u] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = lin[u]; i; i = e[i].ne){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y = e[i].y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(e[i].z == 1) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(col[y]) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>col[y] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int dis[MAXN];</p><p style="text-align: left;">void bfs3(int u){</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(dis, INF, sizeof(dis));</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[u] = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>queue<int> q;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(u);</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!q.empty()){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x = q.front(); q.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = lin[x]; i; i = e[i].ne){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y = e[i].y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(e[i].z == 2) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(col[y]) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[y] != INF) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[y] = dis[x] + 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>q.push(y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>read(n), read(m);</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x, y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i <= m; ++i){</p><p style="text-align: left;"><span style="white-space:pre"> </span>read(x), read(y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>add(x, y, 1); add(y, x, 2);//1为正边,2为负边</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>read(st), read(ed);</p><p style="text-align: left;"><span style="white-space:pre"> </span>bfs(ed);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1; i <= n; ++i){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!vis[i]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>bfs2(i);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>bfs3(st);<span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[ed] == INF) puts("-1");</p><p style="text-align: left;"><span style="white-space:pre"> </span>else printf("%d\n", dis[ed]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。