求调代码
查看原帖
求调代码
586924
封禁用户楼主2022/9/16 17:44
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m,s,t,tot=0;
int h[2][N],d[2][N],ok[2][N],vis[N];
struct Node{
	int u;
	int v;
	int nxt;
	bool operator <(const Node &a)const{
		return v>a.v;
	}
}e[2][M];
void add(int o,int u,int v){
	++tot;
	e[o][tot]=(Node){u,v,h[o][u]};
	h[o][u]=tot;
}
void Dijkstra(int o,int s){
	memset(d[o],0x3f,sizeof(d[o]));
	memset(vis,false,sizeof(vis));
	d[o][s]=0;
	if(o)ok[1][s]=true;
	priority_queue<Node>q;
	q.push((Node){s,0,0});
	while(!q.empty()){
		Node p=q.top();
		q.pop();
		int u=p.u;
		if(u==t)return;
		if(vis[u])continue;
		vis[u]=true;
		for(int i=h[o][u];i>0;i=e[o][i].nxt){
			int v=e[o][i].v;
			if(!o&&!ok[0][v])continue;
			if(o)ok[1][v]=true;
			if(d[o][u]+1<d[o][v]){
				d[o][v]=d[o][u]+1;
				q.push((Node){v,d[o][v]});
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		if(u==v)continue;
		add(0,u,v);
		add(1,v,u);
	}
	scanf("%d%d",&s,&t);
	Dijkstra(1,t);
	memcpy(ok[0],ok[1],sizeof(ok[1]));
	for(int i=1;i<=n;++i){
		if(ok[0][i]){
			for(int j=h[0][i];j>0;j=e[0][j].nxt){
				int v=e[0][j].v;
				if(!ok[0][v]){
					ok[0][i]=false;
					break;
				}
			}
		}
	}
	Dijkstra(0,s);
	if(d[0][t]>=0x3f3f3f3f){
		printf("%d",-1);
	}else{
		printf("%d",d[0][t]);
	}
	return 0;
}

PS:0表示正向,1表示反向

2022/9/16 17:44
加载中...