必可赛前公益众筹赛 第一试 D
https://qoj.ac/problem/5034, 2022-2023 集训队互测 Round 6 (Nov 12, 2022)
题目描述
这原本是一道简单的最短路问题,但是由于种种地域文化,宗教信仰以及政治因素,原来一些或许可以行走的路径不能通行了。我们定义禁止路径为连续的经过一些特定的点的路径。一条可爱路径指从 \(1\) 到 \(n\) 的不经过任何禁止路径的路径。给定了一张 \(n\) 个点 \(m\) 条边的有向带权图和 \(k\) 条禁止路径,现在小 Z 想让你求出最短的可爱路径,若不存在输出 \(−1\)。为什么叫做可爱路径呢,因为这道题原来很可爱。\(n, m, k, \sum p\leq 2\times 10^5\)(\(\sum p\) 是禁止路径的长度和)。
solution
因为这个禁止路径的限制像一个匹配,我们直接建 AC 自动机。字符集太大,直接上可持久化线段树计算 Fail 指针以及维护 Trie 图,只需要观察正常 AC 自动机的建法,将其扩展一下即可。现在可以在 AC 自动机上跑 Dijkstra 算法,每次枚举这个状态对应图上的点的出边进行转移(根节点除外,但可以将根节点的 \(n\) 个儿子全部建出来以避免分讨)。因为一个图上的点的出边很可能被枚举多次,所以复杂度 \(O(nm\log m)\)。
为了优化这个算法,观察到有一些边是被重复枚举的。因为 Dijkstra 的性质,每个点取出时的 \(dis\) 不降,所以每条边只有第一次松弛是有效的,只要每条边不被重复枚举我们就赢了。又观察到这些边可以认为是存在可持久化线段树上的,对于每一个状态,其 Trie 图上的儿子,如果有对应图上的边,就可以松弛。而 Trie 图是存在于可持久化线段树中的,每个儿子是可持久化线段树中的一片叶子,而全局叶子的数量不超过 \(O(n+\sum p)\)。我们在可持久化线段树上 dfs,保证每一个线段树节点被访问不超过一次即可。注意对于根节点的 \(n\) 个儿子需要特判,因为根节点对应图上节点不固定,这时候需要另外写东西。维护 \(n\) 个 set,第 \(i\) 个 set 维护图上 \(i\) 节点的出边。每次如果 dfs 到根节点的 \(n\) 个儿子建出的线段树,则将当前状态所在节点的 set 拿出来,暴力找出 set 中在 \([l, r]\) 区间内的出边,转移并删除之。复杂度 \(O(n\log n)\)(认为 \(n, m, \sum p\) 同阶)。
code
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
template <class T>
using pqueue = priority_queue<T, vector<T>, greater<T>>;
namespace seg {/*{{{*/
constexpr int N = 200010 << 5;
int ch[N][2], val[N], tot, tot0;
int mdf(int x, int v, int q, int l, int r) {
int p = ++tot;
ch[p][0] = ch[q][0], ch[p][1] = ch[q][1], val[p] = val[q];
if (l == r) return val[p] = v, p;
int mid = (l + r) >> 1;
if (x <= mid) ch[p][0] = mdf(x, v, ch[q][0], l, mid);
else ch[p][1] = mdf(x, v, ch[q][1], mid + 1, r);
return p;
}
int qry(int x, int p, int l, int r) {
if (!p) return 0;
if (l == r) return val[p];
int mid = (l + r) >> 1;
if (x <= mid) return qry(x, ch[p][0], l, mid);
else return qry(x, ch[p][1], mid + 1, r);
}
};/*}}}*/
int n, m, k, tot, rt[400010], fail[400010], upc[400010];
bool ban[400010], vis[400010];
LL dis[400010];
map<int, int> ch[400010], g[200010], g0[200010];
void build() {/*{{{*/
queue<int> q;
fail[0] = 0;
for (auto&& e : ch[0]) {
int v = e.second, r = e.first;
rt[0] = seg::mdf(r, v, rt[0], 1, n);
fail[v] = 0;
q.push(v);
}
seg::tot0 = seg::tot;
while (!q.empty()) {
int u = q.front(); q.pop();
ban[u] |= ban[fail[u]];
rt[u] = rt[fail[u]];
for (auto&& e : ch[u]) {
int v = e.second, r = e.first;
rt[u] = seg::mdf(r, v, rt[u], 1, n);
fail[v] = seg::qry(r, rt[fail[u]], 1, n);
q.push(v);
}
}
}/*}}}*/
pqueue<pair<LL, int>> q;
void solve(int u, LL pred, int p, int l, int r) {
using seg::val;
if (!p || val[p] == -1) return ;
if (p <= seg::tot0) {
auto it = g0[u].lower_bound(l);
while (it != g0[u].end() && it->first <= r) {
if (pred + it->second < dis[it->first])
q.emplace(dis[it->first] = pred + it->second, it->first);
it = g0[u].erase(it);
}
return ;
}
if (l == r) {
assert(val[p] > 0);
if (g[u].count(l) && pred + g[u][l] < dis[val[p]])
q.emplace(dis[val[p]] = pred + g[u][l], val[p]);
val[p] = -1;
return ;
}
int mid = (l + r) >> 1;
solve(u, pred, seg::ch[p][0], l, mid);
solve(u, pred, seg::ch[p][1], mid + 1, r);
val[p] = -1;
}
LL dijkstra() {
memset(vis, false, sizeof vis);
memset(dis, 0x3f, sizeof dis);
q.emplace(dis[ch[0][1]] = 0, ch[0][1]);
while (!q.empty()) {
int id = q.top().second; q.pop();
if (vis[id] || ban[id]) continue;
vis[id] = true;
debug("dis[%d] = %lld\n", id, dis[id]);
solve(upc[id], dis[id], rt[id], 1, n);
}
LL ans = 1e18;
for (int i = 1; i <= tot; i++) if (!ban[i] && upc[i] == n) ans = min(ans, dis[i]);
return ans >= 1e18 ? -1ll : ans;
}
int main() {
#ifndef LOCAL
#ifndef NF
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
#endif
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) ch[0][i] = ++tot, upc[tot] = i;
for (int i = 1, u, v, w; i <= m; i++) cin >> u >> v >> w, g[u][v] = w;
for (int i = 1; i <= n; i++) g0[i] = g[i];
while (k--) {
int len, p = 0, r;
cin >> len;
while (len--) {
cin >> r;
if (!ch[p].count(r)) ch[p][r] = ++tot, upc[tot] = r;
p = ch[p][r];
}
ban[p] = true;
}
build();
for (int i = 1; i <= tot; i++) debug("fail[%d] = %d\n", i, fail[i]);
for (int i = 1; i <= tot; i++) debug("upc[%d] = %d\n", i, upc[i]);
cout << dijkstra() << endl;
return 0;
}
标签:rt,ch,int,题解,BC2401D,seg,QOJ5034,id,dis
From: https://www.cnblogs.com/caijianhong/p/18432050/solution-QOJ5034