luogu P2296 寻找道路 |最短路

题目描述

在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：

路径上的所有点的出边所指向的点都直接或间接与终点连通。

在满足条件 1 的情况下使路径最短。

注意：图 G 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

输入格式

第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。

接下来的 m 行每行 2 个整数 x,y，之间用一个空格隔开，表示有一条边从点 x 指向点y。

最后一行有两个用一个空格隔开的整数 s, t，表示起点为 s，终点为 t。

输出格式

输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。

预处理所有可以走的点，直接跑最短路

#include<cstdio>

#include<iostream>

#include<queue>

using namespace std;

const int N=1e5+10,M=2e6+10;

int n,m,s,t;

int Next[M],head[N],go[M],tot;

inline void add(int u,int v){

	Next[++tot]=head[u];head[u]=tot;go[tot]=v;

}

struct E{

	int x,y;

}e[M];

bool v1[N],v2[N];

int fa[N];

int get(int x){

	if(x==fa[x])return x;

	else return fa[x]=get(fa[x]);

}

bool bfs(){

	queue<int>q;

	q.push(t);

	v1[t]=1;

	while(q.size()){

		int x=q.front();

		q.pop();

		for(int i=head[x];i;i=Next[i]){

			if(v1[go[i]])continue;

			v1[go[i]]=1;

			q.push(go[i]);

		}

	}

}

int d[N];

struct node{

    int u,d;

    bool operator <(const node& rhs)const{

        return d>rhs.d;

    }

};

void dj(){

	for(int i=1;i<=n;i++)d[i]=1e9;

	priority_queue<node>Q;

	d[s]=0;

	Q.push((node){s,0});

	while(!Q.empty()){

		node ch=Q.top();

		Q.pop();

		int u=ch.u;

		int y=ch.d;

		if(y!=d[u])continue;

		for(int i=head[u];i;i=Next[i]){

			int x=go[i];

			if(v2[go[i]]&&d[u]+1<d[x]){

				d[x]=d[u]+1;

				Q.push((node){x,d[x]});

			}

		}

	}

}

int main(){

	cin>>n>>m;

	for(int i=1;i<=n;i++)fa[i]=i;

	for(int i=1,x,y;i<=m;i++){

		scanf("%d%d",&x,&y);

		if(x==y)continue;

		int a=get(x);

		int b=get(y);

		if(a!=b)fa[a]=b;

		e[i].x=x;e[i].y=y;

		add(y,x);

	}

	cin>>s>>t;

	if(get(s)!=get(t)){

		cout<<-1<<endl;

		return 0;

	}

	bfs();

	for(int i=1;i<=n;i++)head[i]=0;

	for(int i=1;i<=tot;i++)Next[i]=0;

	tot=0;

	for(int i=1;i<=m;i++)

		add(e[i].x,e[i].y);

	for(int i=1;i<=n;i++){

		bool op=1;

		for(int e=head[i];e;e=Next[e]){

			if(v1[go[e]]==0){

				op=0;

				break;

			}

		}

		v2[i]=op;

	}

	dj();

	cout<<d[t];

}

巴特西

luogu P2296 寻找道路 |最短路

题目描述

输入格式

输出格式

最新文章

热门文章