游客 注册 | 登录
中文 | En

3407 - 寻找道路

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

在有向图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

输入/输出样例

输入格式

3 2
1 2
2 1
1 3

输出格式

-1

C++解答

#include <cstdio>
#include <cstring>

#define  maxn  10005LL
#define  maxe  200005LL
#define  infi  0x3f3f3f3fLL
#define  sizeque  20000LL

struct FST{
	int to , next ;
} e[maxe] , re[maxe] ;

int tot = 0 , star[maxn] = {0} ;
void AddEdge(int u , int v) {
	tot ++ ; e[tot].to = v ;
	e[tot].next = star[u] ; star[u] = tot ;
}

int rtot = 0 , rstar[maxn] = {0} ;
void AddrEdge(int u , int v) {
	rtot ++ ; re[rtot].to = v ;
	re[rtot].next = rstar[u] ; rstar[u] = rtot ;
}

int n , m ;
int St , En ;
int dis[maxn] = {0} ;
bool exist[maxn] = {0} ;
bool flag[maxn] = {0} ;

struct Que{
	int q[maxn] , head , tail ;
	int F(int x) { return ((x%sizeque)+sizeque)%sizeque ; }
	int front() { return q[F(head)] ; }
	bool empty() { return head > tail ; }
	void clear() { head = 0 ; tail = -1 ; }
	void pop() { head ++ ; }
	void push_front(int x) { q[F(--head)] = x ; }
	void push_back(int x) { q[F(++tail)] = x ; }
} q ;

void rspfa() {
	memset(dis , 0x3f , sizeof (dis)) ;
	dis[En] = 0 ; q.clear() ; q.push_back(En) ;
	int u , v , p ;
	while (!q.empty()) {
		u = q.front() ; q.pop() ; exist[u] = false ;
		for (p=rstar[u],v=re[p].to;p;p=re[p].next,v=re[p].to) {
			if (dis[v] > dis[u]+1) {
				dis[v] = dis[u]+1 ;
				if (!exist[v]) {
					exist[v] = true ;
					if (dis[v] < dis[q.front()]) q.push_front(v) ;
					else q.push_back(v) ;
				}
			}
		}
	}
	for (u = 1 ; u <= n ; u ++ )
		if (dis[u] == infi) {
			flag[u] = true ;
			for (p=rstar[u],v=re[p].to;p;p=re[p].next,v=re[p].to)
				flag[v] = true ;
		}
}

void spfa() {
	if (flag[St]) {
		puts("-1") ; return ;
	}
	memset(dis , 0x3f , sizeof (dis)) ;
	dis[St] = 0 ; q.clear() ; q.push_back(St) ;
	int u , v , p ;
	while (!q.empty()) {
		u = q.front() ; q.pop() ; exist[u] = false ;
		for (p=star[u],v=e[p].to;p;p=e[p].next,v=e[p].to) {
			if (flag[v]) continue ;
			if (dis[v] > dis[u]+1) {
				dis[v] = dis[u]+1 ;
				if (!exist[v]) {
					exist[v] = true ;
					if (dis[v] < dis[q.front()]) q.push_front(v) ;
					else q.push_back(v) ;
				}
			}
		}
	}
	if (dis[En] == infi) puts("-1") ;
	else printf("%d\n" , dis[En] ) ;
}

int main() {
//	    freopen("road.in" ,"r",stdin ) ;
//	    freopen("road.out","w",stdout) ;
	int i , u , v ;
	scanf("%d%d", &n , &m ) ;
	for (i = 0 ; i < m ; i ++ ) {
		scanf("%d%d", &u , &v ) ;
		AddEdge(u , v) ;
		AddrEdge(v , u) ;
	}
	scanf("%d%d", &St , &En ) ;
	rspfa() ;
	spfa() ;
	    fclose(stdin ) ; fclose(stdout) ;
	return 0 ;
}
请先登陆