题目描述
在有向图 GGG 中，每条边的长度均为 111，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
- 路径上的所有点的出边所指向的点都直接或间接与终点连通。
- 在满足条件1 1 1的情况下使路径最短。
注意：图 GGG 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入输出格式
输入格式：第一行有两个用一个空格隔开的整数 nnn 和 mmm，表示图有 nnn 个点和 mmm 条边。
接下来的 mmm 行每行 222 个整数 x,yx,yx,y，之间用一个空格隔开，表示有一条边从点 xxx 指向点yyy。
最后一行有两个用一个空格隔开的整数 s,ts, ts,t，表示起点为 sss，终点为 ttt。
输出格式：输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出−1-1−1。
输入输出样例
说明
解释1：
如上图所示，箭头表示有向道路，圆点表示城市。起点11 1与终点33 3不连通，所以满足题目描述的路径不存在，故输出−1-1−1 。
解释2：
如上图所示，满足条件的路径为11 1- >333- >444- >555。注意点222 不能在答案路径中，因为点222连了一条边到点666 ，而点666 不与终点555 连通。
【数据范围】
对于30%30\%30%的数据，0<n≤100 < n \le 100<n≤10，0<m≤200 < m \le 200<m≤20;
对于60%60\%60%的数据，0<n≤1000 < n \le 1000<n≤100，0<m≤20000 < m \le 20000<m≤2000;
对于100%100\%100%的数据，0<n≤10000,0<m≤200000,0<x,y,s,t≤n,x,s≠t0 < n \le 10000, 0 < m \le 200000,0 < x,y,s,t \le n, x,s \ne t0<n≤10000,0<m≤200000,0<x,y,s,t≤n,x,s≠t。
思路是很好想的我感觉
- 找出所有不能到达终点的点
- 将出边是不能到达终点的点的点删掉
- 加入没有删掉的点
- 跑最短路
值得一提的是:
将出边是不能到达终点的点的点删掉,我用了一个数组fa(字面意思),然而由于做树的题目太多了忘记了一个点可以有多个入点
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#define maxn 410000
using namespace std ;
int read() {
int x = 0 , f = 1 ; char s = getchar() ;
while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ;}
while(s <='9' && s >='0') {x = x * 10 + (s-'0'); s = getchar() ;}
return x*f ;
}
int n , m ;
typedef pair<int,int>pa ;
struct dy {
int x , y , z , next ;
}b[maxn] , a[maxn] ;
int t , head[maxn] , vis[maxn] , dis[maxn] , s , st , book[maxn] ;
vector<int>fa[11000] ;
priority_queue<pa ,vector<pa> , greater<pa> > q ;
inline void Add(int x ,int y) {
b[++t].x = x ;
b[t].y = y ;
b[t].next = head[x] ;
head[x] = t;
}
void add(int x,int y) {
a[++t].x = x ;
a[t].y = y ;
a[t].z = 1 ;
a[t].next = head[x] ;
head[x] = t ;
}
void dfs(int x) {
if(vis[x]) return ;
vis[x] = 1 ;
for(int i = head[x] ; i ; i = b[i].next) {
int v = b[i].y ;
if(!vis[v]) {
dfs(v) ;
}
}
}
void dij(int s) {
memset(vis,0,sizeof(vis)) ;
memset(dis,0x3f,sizeof(dis)) ;
dis[s] = 0 , vis[s] = 0 ;
q.push(make_pair(dis[s],s)) ;
while(!q.empty()) {
int u = q.top().second ;
q.pop() ;
if(vis[u]) continue ;
vis[u] = 1 ;
for(int i = head[u] ; i ; i = a[i].next) {
int v = a[i].y ;
if(dis[v] > dis[u] + a[i].z) {
dis[v] = dis[u] + a[i].z ;
q.push(make_pair(dis[v],v)) ;
}
}
}
}
int main () {
n = read() , m = read() ;
for(int i = 1 ; i <= m ; i ++) {
int x = read() , y = read() ;
Add(y,x) ;
fa[y].push_back(x) ;
}
s = read() , st = read();
dfs(st);
for(int i = 1 ; i <= n ; i ++) {
if(!vis[i])
for(int j = 0 ; j < fa[i].size() ; j ++) {
book[fa[i][j]] = 1 ;
}
}
for(int i = 1 ; i <= n ; i ++) {
if(book[i]) vis[i] = 0 ;
}
for(int i = 1 ; i <= n ; i ++)
t = 0 ;
memset(head,0,sizeof(head)) ;
for(int i = 1 ; i <= m ; i ++) {
if(vis[b[i].x]) {
add(b[i].y,b[i].x) ;
}
}
dij(s) ;
printf("%d\n",dis[st]>=dis[n+1] ? -1:dis[st]) ;
return 0 ;
}
京公网安备 11010502036488号