POI2009 WIE-Hexer

题意简述

一个 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));
}
}
}
}
查看评论