0pts,求助
查看原帖
0pts,求助
1048767
WJX114514楼主2024/10/24 19:57
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n,m,ss,t;
int dis[maxn];
bool vis[maxn],cango[maxn];
struct node{
	int to,w;
	node(int t,int ww){
		to=t; w=ww;
	}
};
vector<node> vec[maxn];
vector<int> fa[maxn];
struct qnode{
	int id,d;
	qnode(int x,int y){
		id=x; d=y;
	}
	bool friend operator <(qnode a,qnode b){
		return a.d>b.d;
	}
};
int dij(int ss){
	priority_queue<qnode> q;
	memset(dis,0x7f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[ss]=0; q.push(qnode(ss,0));
	while(!q.empty()){
		int u=q.top().id; q.pop();
		if(vis[u]==true) continue;
		vis[u]=true;
		for(int i=0;i<vec[u].size();i++){
			int v=vec[u][i].to;
			if(dis[v]>dis[u]+vec[u][i].w){
				dis[v]=dis[u]+vec[u][i].w;
				q.push(qnode(v,dis[v]));
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<vec[i].size();j++){
			if(dis[vec[i][j].to]>=0x7f||cango[vec[i][j].to]==false){
				cango[i]=false; cnt++;
			}
		}
		if(cnt>=vec[i].size()){
			for(int j=0;j<fa[i].size();j++) cango[fa[i][j]]=false;
		}
	}
}
priority_queue<qnode> q;
void dij1(int ss){
	memset(dis,0x7f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[ss]=0; q.push(qnode(ss,0));
	while(!q.empty()){
		int u=q.top().id; q.pop();
		if(vis[u]==true||cango[u]==false) continue;
		vis[u]=true;
		for(int i=0;i<vec[u].size();i++){
			int v=vec[u][i].to;
			if(dis[v]>dis[u]+vec[u][i].w){
				dis[v]=dis[u]+vec[u][i].w;
				q.push(qnode(v,dis[v]));
			}
		}
	}
}
int main(){
	memset(cango,true,sizeof(true));
	cin>>n>>m>>ss>>t;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		vec[u].push_back(node(v,1));
		fa[v].push_back(u);
	}
	dij(ss);
	dij1(ss);
	if(dis[t]>=0x7f) cout<<"-1";
	else cout<<dis[t];
	return 0;
}

不知道哪里的问题

2024/10/24 19:57
加载中...