0魔法阵 - 蓝桥云课 (lanqiao.cn)
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define x first
#define y second
const int N = 1010;
const int inf = 1e4;
vector<pair<int,int>> a[N];
int f[N][20];
int st[N];
int main(){
int n,k,m;
cin>>n>>k>>m;
int u,v,w;
while(m--){
cin>>u>>v>>w;
a[u].push_back({v,w});
a[v].push_back({u,w});
}
queue<int> q;
memset(f,inf,sizeof f);
f[0][0] = 0;
q.push(0);
while(q.size()){
int u = q.front();
q.pop();
st[u] = 0;
for(auto i : a[u]){
int v = i.first;
int w = i.second;
bool flag = false;
if(f[v][0]>f[u][0]+w){
f[v][0] = f[u][0]+w;
flag = true;
}
for(int i = 1;i<=k;i++){
if(f[v][i]>f[u][i-1]){
f[v][i] = f[u][i-1];
flag = true;
}
}
if(f[v][k]>f[u][k]+w){
flag = true;
f[v][k] = f[u][k]+w;
}
if(flag&&!st[v]){
q.push(v);
st[v] = 1;
}
}
}
cout<<min(f[n-1][k],f[n-1][0]);
return 0;
}