大雾
  • 板块灌水区
  • 楼主zouyuhao20120225
  • 当前回复12
  • 已保存回复12
  • 发布时间2024/7/15 18:06
  • 上次更新2024/7/15 19:12:57
查看原帖
大雾
815807
zouyuhao20120225楼主2024/7/15 18:06
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

const int N=100005,INF=2147483647;
int dis[N],vis[N],s,t,n,m,x,y,w; 
struct quan{
	int d,v; 
	bool operator>(const quan a) const{return d>a.d;}
};
priority_queue<quan,vector<quan>,greater<quan> > q;
struct bian{
	int v,w;
}; 
vector<bian> e[N];
void Dijkstra(){
	while(!q.empty()){
		int u=q.top().v;
		q.pop(); 
		if(vis[u]) continue;
		vis[u]=1;
		for(auto ed:e[u]){
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
}
int main(){
	scanf("%d %d %d\n%d\n",&n,&m,&s,&t);
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[s]=1;
	for(int i=1;i<=m;i++){
		scanf("%d %d\n",&x,&y);
		e[x].push_back({y,1}); 
		e[y].push_back({x,1});
	}
	q.push({1,s});
	Dijkstra();
	int mx=-1;
	for(int i=1;i<=n;i++){
		mx=max(mx,dis[i]);
	} 
	cout<<mx+t;
	return 0;
}

样例:

4 3 1
2
1 2
1 3
2 4

为什么我的代码要多输入一个数字才能结束?

2024/7/15 18:06
加载中...