「JSOI2010」汇总

标签：路径   次数   https   read   printf   ext   mat   cto   oid   

「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 
#include 
#include 
#include 
#include 
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0'  vec[_];

struct node { int u[2], w; } p[__];
inline bool cmp(const node& x, const node& y) { return x.w  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  dp[u.i][u.j][u.k] + p[u.j + 1].w && u.j  dp[u.i][u.j][u.k] + p[u.j + 1].w && u.j  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 

「JSOI2010」汇总

标签：路径   次数   https   read   printf   ext   mat   cto   oid   

原文地址：https://www.cnblogs.com/zsbzsb/p/12244368.html