| 题目名称 | 1807. [NOIP 2014]寻找道路 |
|---|---|
| 输入输出 | roadb.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2014-11-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：379， 提交：1108， 通过率：34.21% | ||||
 TARDIS |
100 | 0.007 s | 0.16 MiB | C++ |
 Furyton |
100 | 0.016 s | 1.09 MiB | C++ |
 BaDBoY |
100 | 0.022 s | 0.43 MiB | C++ |
 Hzoi_Mafia |
100 | 0.026 s | 0.71 MiB | C++ |
|
BaDBoY |
100 | 0.026 s | 0.71 MiB | C++ |
 LGLJ |
100 | 0.029 s | 0.97 MiB | C++ |
 ImwaOuKur |
100 | 0.031 s | 0.77 MiB | C++ |
 dateri |
100 | 0.044 s | 0.16 MiB | C++ |
 Arrow |
100 | 0.044 s | 0.43 MiB | C++ |
|
Arrow |
100 | 0.044 s | 0.54 MiB | C++ |
| 本题关联比赛 | |||
| EYOI常规赛9 3/4th | |||
| EYOI常规赛10th | |||
| EYOI的落幕/崛起 | |||
| 关于 寻找道路 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
反向BFS+标记+正向BFS+查标记==10分钟AC
| ||||
|
正反bfs毫无压力
 不需要黄桃
2017-11-02 22:14
28楼
| ||||
|
记住松弛了才能入队马丹
| ||||
|
要是联赛就完了
 天亮说晚安·
2017-09-17 10:54
26楼
| ||||
|
一个dfs一个spfa。贼简单
| ||||
|
第一次交只拿了30分，原来是访问标记忘打了，AC与AFO就在一念之间。。
| ||||
|
1A开心~就是反向建边跑bfs找出可以到达终点的点，然后再从起点跑一遍bfs找最短路
 Shirry
2017-09-03 20:39
23楼
| ||||
|
| ||||
|
回复 @Metatron :
结果还错了  +1s
2017-07-01 10:44
21楼
| ||||
|
回复 @Metatron :
我跑了三遍 +1s
2017-07-01 10:43
20楼
| ||||
snake
据说这是zzy
하루Kiev 
Hallmeow【题目描述】
在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2．在满足条件 1 的情况下使路径最短。
注意：图 G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
【输入格式】
第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x、y，之间用一个空格隔开，表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 s、t，表示起点为 s，终点为 t。
【输出格式】
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。
【样例输入1】
3 2 1 2 2 1 1 3
【样例输出1】
-1
【样例1说明】
如上图所示，箭头表示有向道路，圆点表示城市。起点 1 与终点 3 不连通，所以满足题目描述的路径不存在，故输出-1。
【样例输入2】
6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5
【样例输出2】
3
【样例2说明】
如上图所示，满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中，因为点 2连了一条边到点 6，而点 6 不与终点 5 连通。
【数据规模与约定】
对于 30%的数据，$0<n\leq 10,0<m\leq 20$；
对于 60%的数据，$0<n\leq 100,0<m\leq 2000$；
对于 100%的数据，$0<n\leq 10,000,0<m\leq 200,000,0<x,y,s,t\leq n,x\neq t$。
【来源】
NOIP2014 Day2 Task2