题目
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int inf = 0x3f3f3f3f;
int g[N][N], d[N][N];
bool st[N][N];
int n, k, m;
struct Node
{int v, c, i;bool operator < (const Node &y) const{return v > y.v;}
};
priority_queue<Node> pq;
void dijkstra()
{memset(d, 0x3f, sizeof d);pq.push({0, 0, 0});d[0][0] = 0;while(pq.size()){auto u = pq.top(); pq.pop();int v = u.v, c = u.c, i = u.i;if(st[c][i]) continue;st[c][i] = 1;for(int j = 0; j < n; j++){if(g[i][j] == inf) continue;if(d[j][0] > d[i][0] + g[i][j]){d[j][0] = d[i][0] + g[i][j];pq.push({d[j][0], 0, j});}if(c == k){if(d[j][k] > d[i][k] + g[i][j]){d[j][k] = d[i][k] + g[i][j];pq.push({d[j][k], k, j});}}if(c+1 <= k && d[j][c+1] > d[i][c]){d[j][c+1] = d[i][c];pq.push({d[j][c+1], c+1, j});}}}}
int main()
{ios::sync_with_stdio(0); cin.tie(0);memset(g, 0x3f, sizeof g);cin >> n >> k >> m;for(int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;g[a][b] = c;g[b][a] = c;}dijkstra();cout << min(d[n-1][0], d[n-1][k]);
}
