19 pts 悬关求调
查看原帖
19 pts 悬关求调
969221
Fryderyk_Chopin楼主2025/7/3 22:14
#include<bits/stdc++.h>

using namespace std;

const int MAXN=2e9,N=10000;
int n,m,p;
int st,en,vis[11][20010],num[20010],dis[11][20010];
struct Graph{
	int to,w,dep;
	bool operator <(const Graph &x)const{
		return x.dep<dep && x.w<w;
	}
	bool operator >(const Graph &x)const{
		return x.dep>dep && x.w>w;
	}
};
vector<Graph>g[20010];
priority_queue<Graph>q;

int main(){
	cin>>n>>m>>p;
	cin>>st>>en;
	for(int i=0;i<=p;i++) for(int j=0;j<n;j++) dis[i][j]=MAXN;
	for(int i=1,x,y,w;i<=m;i++){
		cin>>x>>y>>w;
		g[x].push_back({y,w,0});
		g[y].push_back({x,w,0});
	}
	dis[0][st]=0;
	q.push({st,0,0});
	while(!q.empty()){
		Graph k=q.top();
		q.pop();
		if(vis[k.dep][k.to]) continue;
		vis[k.dep][k.to]=1;
		for(Graph i:g[k.to]){
			if(dis[k.dep][k.to]+i.w<dis[k.dep][i.to]){
				dis[k.dep][i.to]=dis[k.dep][k.to]+i.w;
				if(!vis[k.dep][i.to]) q.push({i.to,dis[k.dep][i.to],k.dep});
			}
			if(k.dep<p){
				if(dis[k.dep+1][i.to]>dis[k.dep][k.to]){
					dis[k.dep+1][i.to]=dis[k.dep][k.to];
					if(!vis[k.dep+1][i.to]) q.push({i.to,dis[k.dep+1][i.to],k.dep+1});
				}
			}
		}
	}
	int ans=2e9;
 	for(int i=0;i<=p;i++) ans=min(ans,dis[i][en]);
 	cout<<ans;
	return 0;
}

hack 能过,样例没问题。 谢谢好心人出手相助!

2025/7/3 22:14
加载中...