10pts,其它MLE,(玄关)!!!
查看原帖
10pts,其它MLE,(玄关)!!!
774204
A_chicken_boy楼主2024/8/21 14:13
#include <bits/stdc++.h>
using namespace std ;
const int N= 2e5 + 100 ;
const int M = 1e4 + 1 ;
priority_queue< pair<int,int> > q ;
int n , m ;
int tot , ver[N] , st[N] , edge[N] , ne[N] , head[N] ;
int tot2 , ver2[N] , st2[N] , edge2[N] , ne2[N] , head2[N] ;
int d[M] ;
int p[M] , pd[M] ;
int u , v ;
int f[M] , f2[M] ;
int s , t ;
int mp[10004][10004] ;
void add ( int x , int y , int z ){
	ver[++tot] = y ;
	st[tot]= x ;
	edge[tot] = z ;
	ne[tot] = head[x] ;
	head[x] = tot ;
	ver2[++tot2] = x ;
	st2[tot2] = y ;
	edge2[tot2] = z ;
	ne2[tot] = head2[y] ;
	head2[y] = tot ;
}
void dfs ( int x ){
	for ( int i = head2[x] ; i ; i = ne2[i] ){
		int y = ver2[i] ;
		f[y] = 1 ;
		dfs ( y ) ;
	}
}
int main ( ){
	//freopen ( "road.in" , "r" , stdin ) ;
	//freopen ( "road.out" , "w" , stdout ) ;
	cin >>n >>m ;
	for ( int i = 0 ; i <= 2 * n ; ++i ){
		d[i] = INT_MAX-1;
	}
	for ( int i =1  ; i <= m ; ++i ){
		cin >>u >> v ;
		add(u,v,1) ;
		mp[u][v] = 1 ;
	}
	cin >> s >> t ;
	dfs ( t ) ;
	f[t] = 1 ;	
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = 1 ; j <= n ; ++j ){
			if ( mp[i][j] == 1 && f[j] == 0 ){
				f2[i] = 3 ;
			}
		}
	}
	d[s] = 0 ;
	q.push(make_pair(0,s)) ;
	while ( q.size( ) ){
		int x = q.top( ).second ;
		q.pop() ;		
		if ( p[x] || f2[x] == 3 ) continue ;
		p[x] = 1 ;
		for ( int i = head[x] ; i ; i = ne[i] ){
			int y = ver[i] , z = edge[i] ;
			if ( d[y] > d[x] + z ){
				d[y] = d[x] + z ;
				q.push(make_pair(-d[y],y)) ;
			}
		}
	}
	if ( d[t] == INT_MAX - 1 ){
		cout << "-1" ;
		return 0 ;
	}
	cout << d[t] ;
	return 0 ;
}
/*
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
*/
2024/8/21 14:13
加载中...