这道题我用的是类似dp的办法 设disTo（i,j）表示从源点到i,恰好使用j次SpellCard的最短路长度。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int n,m,k,minn = 0x7fffffff;
struct nod{
	int next,val;
	bool operator <(const nod &x)const{
        return val > x.val;
	}
};
vector <nod> V[1005];
int disTo[1005][1005];
bool vis[1005];
priority_queue <nod> pq;
void dijkstra(){
	//memset(vis,0,sizeof vis);
	memset(disTo,0x3f,sizeof disTo);
	pq.push((nod){1,0});
	for(int i = 0;i <= k;i++)
		disTo[1][i] = 0;
	while(!pq.empty()){
		nod nx = pq.top();
		pq.pop();
		for(int i = 0;i < V[nx.next].size();i++){
			for(int j = 0;j <= k;j++){
				int xx = V[nx.next][i].next;
				if(disTo[nx.next][j] + V[nx.next][i].val < disTo[xx][j]){//核心转移
					disTo[xx][j] = disTo[nx.next][j] + V[nx.next][i].val;
					if(j > 0 && disTo[nx.next][j - 1] + (V[nx.next][i].val) / 2 < disTo[xx][j])
						disTo[xx][j] = disTo[nx.next][j - 1] + (V[nx.next][i].val) / 2;
					pq.push((nod){xx,disTo[xx][j]});
				}
			}
		}
	}
}
int main(){
	cin >> n >> m >> k;
	for(int i = 1;i <= m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		V[u].push_back(nod{v,w});
		V[v].push_back(nod{u,w});
	}
	dijkstra();
	for(int i = 0;i <= k;i++)
		minn = min(minn,disTo[n][i]);
	cout << minn;
	return 0;
}