题目描述
在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
路径上的所有点的出边所指向的点都直接或间接与终点连通。
在满足条件 1的情况下使路径最短。
注意：图 G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入输出格式
输入格式：
第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x,y，之间用一个空格隔开，表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 s, t，表示起点为 s，终点为 t。
输出格式：
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出−1。
输入输出样例
输入样例1：
|
1 2 3 4 5 |
3 2 1 2 2 1 1 3 |
输出样例1：
|
1 2 |
-1 |
输入样例2：
|
1 2 3 4 5 6 7 8 9 |
6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5 |
输出样例2：
|
1 2 |
3 |
说明
解释1：
如上图所示，箭头表示有向道路，圆点表示城市。起点1 1与终点3 3不连通，所以满足题目描述的路径不存在，故输出−1 。
解释2：
如上图所示，满足条件的路径为1- >3- >4- >5。注意点2 不能在答案路径中，因为点2连了一条边到点6 ，而点6不与终点5 连通。
数据范围
对于30%的数据,\(\) 0
对于60%的数据0
对于100%的数据0
题解
- 反向建边
- 从结束点开始遍历图
- 标记没有遍历到的点的出边的点为不合法的点
- 最短路
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; const int MAXN =200005; int Nt[MAXN],Head[MAXN],to[MAXN],tot; int x[MAXN],y[MAXN],d[MAXN],f[MAXN]; bool vis[10003]; int n,m,s,t; bool v[10003]; void add(int a,int b){ Nt[++tot]=Head[a]; to[tot]=b; Head[a]=tot; } void dfs(int x){ v[x]=1; for(int i=Head[x];i;i=Nt[i]){ int y=to[i]; if(v[y])continue; dfs(y); } } priority_queue<pair<int,int> > q; void dij(){ memset(d,0x3f,sizeof(d)); memset(vis,0,sizeof(vis)); d[t]=0; q.push(make_pair(0,t)); while(q.size()){ int x=q.top().second;q.pop(); if(vis[x]==1||f[x]==1)continue; vis[x]=1; for(int i=Head[x];i;i=Nt[i]){ int y=to[i]; if(d[y]>d[x]+1){ d[y]=d[x]+1; q.push(make_pair(-d[y],y)); } } } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d",&x[i],&y[i]); if(x[i]==y[i])continue;//忽略自环 add(y[i],x[i]); } cin>>s>>t; dfs(t); for(int i=1;i<=n;i++) if(v[i]==0) for(int j=Head[i];j;j=Nt[j])f[to[j]]=1; dij(); if(d[s]==0x3f3f3f3f)cout<<-1<<endl; else cout<<d[s]<<endl; return 0; } |
评论