标签：

「JSOI2010」旅行

传送门
对照妙的一道 \(\text{DP}\) 题，思维瓶颈应该就是如何确定状态。
首先将边按边权排序。
如果我们用 \(01\) 串来暗示 \(m\) 条边是否在路径上，，那么我们就可以通过钦定前 \(x\) 条边在路径上来确定方针状态。
此中有的边消耗了魔法使用次数，有的没消耗。
那么我们就可以设 \(dp[i][j][k]\) 暗示到点 \(i\) ，颠末了前 \(j\) 条被钦定边，并且使用了 \(k\) 次魔法的最短路，那么转移就是（假设我们此刻要从点 \(u\) 走到点 \(v\)）：
如果当前这条边是被钦定的边：\(dp_{u, j, k} + w_{j + 1} \to dp_{v, j + 1, k}\)
如果当前这条边不是被钦定的边：

用魔法：\(dp_{u, j, k} + w_{j + 1} \to dp_{v, j + 1, k + 1}\)

不用魔法：\(dp_{u, j, k} + dis(u, v) \to dp_{v, j, k}\)

参考代码：

#include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) using namespace std; template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } const int _ = 52, __ = 152; int n, m, k, ans = 2147483647; vector < int > vec[_]; struct node { int u[2], w; } p[__]; inline bool cmp(const node& x, const node& y) { return x.w < y.w; } struct DP { int i, j, k; } ; inline void calc(int x) { static queue < DP > Q; static int exi[_][__][_], dp[_][__][_]; memset(dp, 0x3f, sizeof dp); dp[1][0][0] = 0, Q.push((DP) { 1, 0, 0 }); while (!Q.empty()) { DP u = Q.front(); Q.pop(), exi[u.i][u.j][u.k] = 0; for (rg int i = 0; i < vec[u.i].size(); ++i) { int id = vec[u.i][i], v = p[id].u[u.i == p[id].u[0]]; if (id <= x) { if (dp[v][u.j + 1][u.k] > dp[u.i][u.j][u.k] + p[u.j + 1].w && u.j < x) { dp[v][u.j + 1][u.k] = dp[u.i][u.j][u.k] + p[u.j + 1].w; if (!exi[v][u.j + 1][u.k]) exi[v][u.j + 1][u.k] = 1, Q.push((DP) { v, u.j + 1, u.k }); } } else { if (dp[v][u.j + 1][u.k + 1] > dp[u.i][u.j][u.k] + p[u.j + 1].w && u.j < x && u.k < k) { dp[v][u.j + 1][u.k + 1] = dp[u.i][u.j][u.k] + p[u.j + 1].w; if (!exi[v][u.j + 1][u.k + 1]) exi[v][u.j + 1][u.k + 1] = 1, Q.push((DP) { v, u.j + 1, u.k + 1 }); } if (dp[v][u.j][u.k] > dp[u.i][u.j][u.k] + p[id].w) { dp[v][u.j][u.k] = dp[u.i][u.j][u.k] + p[id].w; if (!exi[v][u.j][u.k]) exi[v][u.j][u.k] = 1, Q.push((DP) { v, u.j, u.k }); } } } } for (rg int i = 0; i <= k; ++i) ans = min(ans, dp[n][x][i]); } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n), read(m), read(k); for (rg int u, v, w, i = 1; i <= m; ++i) read(u), read(v), read(w), p[i] = (node) { u, v, w }; sort(p + 1, p + m + 1, cmp); for (rg int i = 1; i <= m; ++i) vec[p[i].u[0]].push_back(i), vec[p[i].u[1]].push_back(i); for (rg int i = 0; i <= m; ++i) calc(i); printf("%d\n", ans); return 0; }

「JSOI2010」汇总