https://www.luogu.com.cn/problem/U461173

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+7;
struct node{
	int to,val;
};
vector<node> G[N];
int n,m,s,k;
int sum[N],lsum[N];
bool fl[N];
priority_queue<pair<int,int> > q;
void init(){
	memset(sum,0x3f,sizeof sum);
	sum[1]=0;
	q.push(make_pair(0,1));
}
void dji(){
	while(!q.empty()){
		pair<int,int> l=q.top();
		q.pop();
		if(fl[l.second]) continue;
		fl[l.second]=1;
		for(node v:G[l.second]){
			if(sum[v.to]>sum[l.second]+v.val){
				sum[v.to]=sum[l.second]+v.val;
				q.push(make_pair(-sum[v.to],v.to));
			}
		}
	}
}
signed main(){
	freopen("jump.in","r",stdin);
	freopen("jump.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>s>>k;
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	if(s==1){
		int l=log2(n+1);
		if((1<<l)==(n+1)){
			for(int i=2;i<n;i++){
				G[i].push_back({1,0});
				G[1].push_back({i,0});
			}
			for(int i=1;i<n;i++){
				G[i].push_back({n,k*(i&n)});
				G[n].push_back({i,k*(i&n)});
			}
			init();
			dji();
			for(int i=2;i<=n;i++) cout<<sum[i]<<' ';
		}
		else for(int i=2;i<=n;i++) cout<<"0 ";
	}
	else if(s==2){
		int l=log2(n);
		for(int i=1;i<=n;i++){
			for(int j=0;j<=l;j++){
				if(i&(1<<j)){
					int v=i^(1<<j);
					if(v>=1&&v<=n){
						G[v].push_back({i,k*(1<<j)});
						G[i].push_back({v,k*(1<<j)});
					}
				}
			}
		}
		init();
		dji();
		for(int i=2;i<=n;i++) cout<<sum[i]<<' ';
	}
	else{
		for(int i=2;i<=n;i++){
			G[i].push_back({1,k*(i|1)});
			G[1].push_back({i,k*(i|1)});
		}
		init();
		dji();
		memset(lsum,0x3f,sizeof lsum);
		for(int i=1;i<=n;i++){
			lsum[i]=sum[i];
			for(int j=1;j<i;j<<=1){
				if(i&j) lsum[i]=min(lsum[i],lsum[i^j]);
			}
			sum[i]=min(sum[i],lsum[i]+k*i);
			q.push({-sum[i],i});
		}
		memset(fl,0,sizeof fl);
		dji();
		for(int i=2;i<=n;i++) cout<<sum[i]<<' ';
	}
	return 0;
}

附件是第一个测试点，在本地运行后生成的 jump.out 文件与 ans.out 不一致（由fc得到）。

求指正