【noip2014】寻找道路
题目描述 Description
在有向图G中&＃xff0c;每条边的长度均为1&＃xff0c;现给定起点和终点&＃xff0c;请你在图中找一条从起点到终点的路径&＃xff0c;该路径满足以下条件&＃xff1a;
1&＃xff0e;路径上的所有点的出边所指向的点都直接或间接与终点连通。
2&＃xff0e;在满足条件1的情况下使路径最短。
注意&＃xff1a;图G中可能存在重边和自环&＃xff0c;题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入描述 Input Description
第一行有两个用一个空格隔开的整数n和m&＃xff0c;表示图有n个点和m条边。
接下来的m行每行2个整数x、y&＃xff0c;之间用一个空格隔开&＃xff0c;表示有一条边从点x指向点y。
最后一行有两个用一个空格隔开的整数s、t&＃xff0c;表示起点为s&＃xff0c;终点为t。
输出描述 Output Description
输出文件名为road.out。
输出只有一行&＃xff0c;包含一个整数&＃xff0c;表示满足题目描述的最短路径的长度。如果这样的路径不存在&＃xff0c;输出-1。
样例输入 Sample Input
| road.in | road.out |
| 3 2 1 2 2 1 1 3 | &＃xff0d;1 |
样例输出 Sample Output
| road.in | road.out |
| 6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5 | 3 |
数据范围及提示 Data Size & Hint
对于30%的数据&＃xff0c;0< n ≤10&＃xff0c;0< m ≤20&＃xff1b;
对于60%的数据&＃xff0c;0< n ≤100&＃xff0c;0< m ≤2000&＃xff1b;
对于100%的数据&＃xff0c;0< n ≤10,000&＃xff0c;0< m ≤200,000&＃xff0c;0< x,y,s,t≤n&＃xff0c;x≠t。
下午调了两个小时四十分钟&＃61; &＃61;叫我傻逼
因为之前的思路错了&＃xff0c;我刚开始认为直接做广搜&＃xff0c;然后搜到一个点再做一次dfs&＃xff0c;结果代码非常麻烦&＃xff0c;而且TLE
之后才想明白&＃xff0c;先反向建图&＃xff0c;然后做一遍SPFA或dfs&＃xff0c;看看那些点和终点可以连通&＃xff0c;然后再做广搜&＃61; &＃61;
wok叫我傻逼&＃61; &＃61;
【代码】
#include
#include
#include
#define MAXN 200005
#define maxn 10005
using namespace std;
int n,m,x,y,s,t,head,tail;
int p[maxn];
bool bb[maxn];
struct hp{int num,step;
}queue[maxn];
int v[MAXN],next[MAXN],point[maxn],a[MAXN],b[MAXN];
void dfs(int x){for (int i&＃61;point[x];i;i&＃61;next[i])if (!p[v[i]]){p[v[i]]&＃61;1;dfs(v[i]);}
}
bool check(int x){bool pd&＃61;true;for (int i&＃61;point[x];i;i&＃61;next[i])if (!p[v[i]]){pd&＃61;false; break;}return pd;
}
int main(){scanf("%d%d",&n,&m);for (int i&＃61;1;i<&＃61;m;&＃43;&＃43;i){scanf("%d%d",&y,&x);v[i]&＃61;y;next[i]&＃61;point[x];point[x]&＃61;i;a[i]&＃61;y; b[i]&＃61;x;}scanf("%d%d",&s,&t);p[t]&＃61;1;dfs(t);memset(next,0,sizeof(next));memset(point,0,sizeof(point));memset(v,0,sizeof(v));for (int i&＃61;1;i<&＃61;m;&＃43;&＃43;i){x&＃61;a[i]; y&＃61;b[i];v[i]&＃61;y;next[i]&＃61;point[x];point[x]&＃61;i;}head&＃61;0;tail&＃61;1;queue[tail].num&＃61;s;queue[tail].step&＃61;0;while (head}
京公网安备 11010802041100号