题意

有任意k条边可以免费的dijkstra。

思路

都说了是dijkstra就跑dijkstra先，跑完再说。

跑完之后发现有个免费的问题需要处理。

那就给dijkstra数组加上一维。

f[i][j]表示从s出发，免了j条边的费到i的最少费用。

每次dijkstra的时候循环一遍，处理f[u][所有j]。如果有需要push就做标记最后再push。

最后输出f[t]的最小值即可。

自己钻研出来的野路子，可能不是最优解，有望指正。

代码

#include<iostream>
#include<vector>
#include<queue>
#define N 20000
#define K 20
#define inf 2147483647
#define halfinf 1073741823
using namespace std;
struct edge{
	int v,w;
};
vector<edge>a[N];
int f[N][K];
int n,m,k,s,t;
int main();
void build();
void dijkstra();
void init();
int main(){
	build();
	dijkstra();
	int ans=inf;
	for(int i=0;i<=k;i++)
		ans=min(ans,f[t][i]);//输出f[t]的最小 
	cout<<ans;
	return 0;
}
void build(){
	cin>>n>>m>>k>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		a[u].push_back({v,w});
		a[v].push_back({u,w});
	}
}
void dijkstra(){
	init();
	f[s][0]=0;
	priority_queue<pair<int,int>>p;
	p.push({0,s});
	while(!p.empty()){
		int u=p.top().second;
		p.pop();
		for(auto i:a[u]){
			int v=i.v,w=i.w,s=inf;
			bool push=false;
			for(int j=0;j<=k;j++){//循环每一个j 
				if(f[v][j]>f[u][j]+w){//不免费 
					f[v][j]=f[u][j]+w;
					push=true;
					s=min(s,f[v][j]);
				}
				if(j+1<=k&&f[v][j+1]>f[u][j]){//免费 
					f[v][j+1]=f[u][j];
					push=true; 
					s=min(s,f[v][j+1]);
				}
			}
			if(push)//统一push 
				p.push({-s,v});
		}
	}
}
void init(){
	for(int i=0;i<N;i++)
		for(int j=0;j<K;j++)
			f[i][j]=halfinf;
}