「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」旅行

「JSOI2010」旅行

最新文章

热门文章