POI2009 WIE-Hexer

十月 16, 2020 1644

题意简述

一个 n 个点 m 条边的无向带权连通图，每条边上有一些不同属性的怪物，每个点有一些铁匠可以帮你打造一些不同属性的大宝剑，对应属性的大宝剑可以击败对应属性的怪物而且不会掉耐久。现在你在 1 号节点，问你安全走到 n 号节点的最小边权和是多少，如果一定到不了输出无解。

一些提示性的数据范围：怪物种类不会超过 13。

解题思路

首先要存每条边和每个点的怪物种类，这个第一想法是二维数组，但是看到怪物种类不超过 13 那就直接状压。

接下来用一个类似分层图的思想，令 dist[i][stat] 表示当前在 i 节点，可打怪的状态为 stat 的最短路径，和分层图一样跑最短路即可

关键代码实现

代码至今没调过，就只放一个 Dijkstra 吧，看看就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int MAXN = 200 + 10;
const int MAXSTAT = (1 << 13) + 10;

struct Edge {
    int v, w, stat;
    Edge(int _v = 0, int _w = 0, int _s = 0) : v(_v), w(_w), stat(_s) {}
    bool operator < (const Edge &th) const {
        return w > th.w;
    }
}; typedef Edge Node;

int n, m, p, k;
int sword[MAXN];
std::vector<Edge> G[MAXN];

bool survive(int mon, int swd) {
    return (swd | (swd ^ mon)) == swd;
    // return (swd | mon) == swd;
    // Probable Alternative: (swd | mon) == swd
}

void dijk() {
    std::priority_queue<Node> q;
    static bool vis[MAXN][MAXSTAT];
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0; q.push(Node(1, 0, 0));
    while (!q.empty()) {
        Node nown = q.top(); q.pop();
        int u = nown.v, regswd = nown.stat, swd = nown.stat | sword[u];
        if (u == n) return;
        if (vis[u][regswd]) continue;
        vis[u][regswd] = true;
        for (auto e : G[u]) {
            int v = e.v, w = e.w, monst = e.stat;
            if (survive(monst, swd) && dp[v][swd] > dp[u][regswd] + w) {
                dp[v][swd] = dp[u][regswd] + w;
                q.push(Node(v, dp[v][swd], swd));
            }
        }
    }
}