20pts求调,样例全过
查看原帖
20pts求调,样例全过
1068781
wangxx2012楼主2025/7/23 10:48
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,t,k,head[1000010],dis[1000010];
struct node{
	int to,next,w;
}e[1000010];
bool vis[10000010];
struct qnode{
	int u,w;
	qnode(int uu,int ww){u=uu;w=ww;}
	friend bool operator <(qnode q1,qnode q2){
		return q1.w>q2.w;
	}
};
void adde(int u,int v,int w){
	e[++k].to=v;
	e[k].w=w;
	e[k].next=head[u];
	head[u]=k;
}
int d(int s){
	priority_queue<qnode> q;
	for(int i=1;i<=n;i++) dis[i]=INT_MAX;
	memset(vis,false,sizeof(vis));
	dis[s]=0; q.push(qnode(s,0));
	while(!q.empty()){
		qnode qn=q.top(); q.pop();
		if(vis[qn.u]) continue;
		vis[qn.u]=1;
		for(int i=head[qn.u];i>0;i=e[i].next){
			int v=e[i].to;
			if(dis[v]>dis[qn.u]+e[i].w){
				dis[v]=dis[qn.u]+e[i].w;
				q.push(qnode(v,dis[v]));
			}
		}
	}
	return dis[t];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v;
		adde(u,v,1);
	}
	cin>>s>>t;
	int x=d(s);
	if(x==2147483647) cout<<-1;
	else cout<<x+1;

	return 0;
	}

2025/7/23 10:48
加载中...