复读官方题解。
考虑除了原图的 \(2^k\) 个点，再建一些辅助点，\((u, i, j)\) 表示前 \(i\) 位中修改了 \(j\) 位得到 \(u\)。那么除了原图的 \(m\) 条边，我们还有下面这些边：
- \(u \xrightarrow{0} (u, 0, 0)\)；
- \(\forall i < k, (u, i, j) \xrightarrow{0} (u, i + 1, j)\)；
- \(\forall i < k, (u, i, j) \xrightarrow{0} (u \oplus 2^i, i + 1, j + 1)\)；
- \((u, k, j) \xrightarrow{a_j} u\)。
到这里可以做 \(O(2^k k^3)\)，但是还不够。
观察这个图，发现非 \(0\) 边仅有 \(O(2^k k)\) 条，于是我们在外层 Dijkstra 的同时，内层对 \(u\) 能到达的所有辅助点跑一遍 BFS，给每个辅助点打上是否被访问过的标记，于是每个辅助点只会被访问一次，又因为非 \(0\) 边仅有 \(O(2^k k)\) 条，所以外层的堆也只会被 push 这么多次。所以时间复杂度就是 \(O(2^k k^2)\)，空间复杂度也是 \(O(2^k k^2)\)。
code
// Problem: P9377 [THUPC 2023 决赛] 百合
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9377
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = (1 << 17) + 50;
ll n, m, K, S, f[maxn], a[maxn];
bool vis[maxn], g[maxn][18][18];
vector<pii> G[maxn];
struct node {
ll u, d;
node(ll a = 0, ll b = 0) : u(a), d(b) {}
};
inline bool operator < (const node &a, const node &b) {
return a.d > b.d;
}
struct wwh {
int u, i, j;
wwh(int a = 0, int b = 0, int c = 0) : u(a), i(b), j(c) {}
};
void solve() {
scanf("%lld%lld%lld", &K, &m, &S);
n = (1 << K);
for (int i = 1; i <= K; ++i) {
scanf("%lld", &a[i]);
}
while (m--) {
ll u, v, d;
scanf("%lld%lld%lld", &u, &v, &d);
G[u].pb(v, d);
G[v].pb(u, d);
}
mems(f, 0x3f);
f[S] = 0;
priority_queue<node> pq;
pq.emplace(S, 0);
while (pq.size()) {
int u = pq.top().u;
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = 1;
for (pii p : G[u]) {
ll v = p.fst, d = p.scd;
if (f[v] > f[u] + d) {
f[v] = f[u] + d;
if (!vis[v]) {
pq.emplace(v, f[v]);
}
}
}
queue<wwh> q;
q.emplace(u, 0, 0);
g[u][0][0] = 1;
while (q.size()) {
int v = q.front().u, i = q.front().i, j = q.front().j;
q.pop();
if (i == K && f[v] > f[u] + a[j]) {
f[v] = f[u] + a[j];
pq.emplace(v, f[v]);
}
if (i < K) {
if (!g[v][i + 1][j]) {
g[v][i + 1][j] = 1;
q.emplace(v, i + 1, j);
}
if (!g[v ^ (1 << i)][i + 1][j + 1]) {
g[v ^ (1 << i)][i + 1][j + 1] = 1;
q.emplace(v ^ (1 << i), i + 1, j + 1);
}
}
}
}
for (int i = 0; i < n; ++i) {
printf("%lld%c", f[i], " \n"[i == n - 1]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}