求助(玄关)
  • 板块题目总版
  • 楼主Danny_chan
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/24 22:19
  • 上次更新2024/10/25 08:21:05
查看原帖
求助(玄关)
1032960
Danny_chan楼主2024/10/24 22:19

优先队列不知道怎么编译错误,。

代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
vector<pair<int,int>>a[500010];
int d[10010][20];
bool f[10010][20];
int st,en;
struct node{
	int s,u,cnt;
};
void dj(){
	memset(d,0x3f,sizeof(d));
	priority_queue<node,vector<node>,greater<node>>q;
	q.push({0,st,0});
	d[st][0]=0;
	while(!q.empty()){
		node t=q.top();
		q.pop();
		int s=t.s,u=t.u,cnt=t.cnt;
		for(int i=0;i<a[u].size();i++){
			int v=a[u][i].first;
			int w=a[u][i].second;
			if(cnt<k&&(d[v][cnt]<d[v][cnt+1])){
				d[v][cnt+1]=d[v][cnt];
				q.push({v,d[v][cnt+1],cnt+1});
			}
			if(d[u][cnt]+w<d[v][cnt]){
				d[v][cnt]=d[u][cnt]+w;
				q.push({v,d[v][cnt],cnt});
			}
		}
	}
}
int main(){
	cin>>n>>m>>k;
	cin>>st>>en;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		x++;
		y++;
		a[x].push_back({y,z});
		a[y].push_back({x,z});
	}	
	dj();
	int maxx=-1e9;
	for(int i=0;i<=k;i++){
		maxx=max(maxx,d[n][i]);
	}
	cout<<maxx<<endl;
	return 0;
}
2024/10/24 22:19
加载中...