题目传送门(BZOJ)
>原文链接<

题解 :

分层图最短路模板题

由于$K$很小, 我们建立$K+1$层的图,

对于每条边, 除了在每层里都要连一条之外, 在相邻两层之间要连一条权值为$\frac{w}{2}$的边.

这样, 从第$i$层走到第$i+1$层, 相当于使用了一次机会.

特别的, 第K层不一定是最优解, 极限情况当$M<K$时, 最后一层是更新不到的, 所以我们可以把所有层的$n$都

向下一层的$n$连一条权值为$0$的边.

代码 :

BZ少一个特判(Luogu AC)

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define P(i, j) ((i-1)*n+j)#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000], *p1, *p2; const int N = 50*51;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}struct Edge { int to, val; Edge *next;}*h[N], e[201000];inline void addEdge(int u, int v, int w) { static int _; Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp;}#define mp make_pairint n, m, K;int f[N];int vis[N];priority_queue<pair<int, int> >q;void Dijkstra() { memset(f, 0x3f, sizeof f); f[1] = 0; q.push(mp(0, 1)); while(!q.empty()) { int u = q.top().second; q.pop(); if(vis[u]) continue; vis[u] = 1; rev(i, u) if(f[i->to] > f[u]+i->val) { f[i->to] = f[u]+i->val; q.push(mp(-f[i->to], i->to)); } }}int main() { n = rd(), m = rd(), K = rd(); for(int i = 1; i <= m; i ++ ) { int u = rd(), v = rd(), w = rd(); for(int k = 1; k <= K; k ++ ) { addEdge(P(k, u), P(k, v), w); addEdge(P(k, v), P(k, u), w); addEdge(P(k, u), P(k+1, v), w >> 1); addEdge(P(k, v), P(k+1, u), w >> 1); } addEdge(P(K+1, u), P(K+1, v), w); addEdge(P(K+1, v), P(K+1, u), w); } Dijkstra(); int ans = 1<<30; for(int i = 1; i <= K+1; i ++ ) ans = min(ans, f[P(i, n)]); printf("%d\n", ans) ;}