题意
一个 (n) 点 (m) 边的有向图，还有一棵 (k) 个节点的 trie ，每条边上有一个字符串，可以用 trie 的根到某个节点的路径来表示。每经过一条边，当前携带的字符串就会变成边上的字符串，经过一条边的代价是边权+边上的字符串和当前字符串的 lcp，问从 1 号点走到所有点的最小代价。
(n,mle 50000, kle 20000)
分析
- 将边看成点，如果有 (e1 ightarrow x ightarrow e2) , 连边 (e1 ightarrow e2) ，代价就是 lcp ，考虑优化建图。
- 实际本题的字典树是一个提示，可以将一个点的子节点按照字符大小遍历，根据后缀数组求 (height) 的性质容易知道两个点 (u,v) 的 lca 就是他们 dfs 序中间的所有相邻点的 lca 的深度最小的那一个
- 这个结论也可以通过点作为 lca 的依据（至少两个子树内有关键点）得到，也就是说一定可以通过这种方式表示出这两个点的lca。所以前缀后缀优化建图即可。
- 复杂度 (O(nlogn)) 。
- 注意可能出现一条出边一条入边的字符串相同的情况，所以每个前缀节点还要直接连向对应的后缀节点。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
int x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 5e5 + 7, inf = 0x7fffffff;
int n, m, ndc, edc, T, k;
int a[N], b[N], c[N], d[N];
vector<int> A[N], B[N];
struct edge {
int lst, to, c;
edge(){}edge(int lst, int to, int c):lst(lst), to(to), c(c){}
};
namespace Trie {
edge e[N];
int edc, tim, pc;
int head[N], in[N], pos[N], mi[N][20], dep[N], Log[N];
void Add(int a, int b) {
e[++edc] = edge(head[a], b, 0), head[a] = edc;
}
void dfs(int u) {
mi[pos[u] = ++pc][0] = u;
in[u] = ++tim;
go(u) {
dep[v] = dep[u] + 1;
dfs(v);
mi[++pc][0] = u;
}
}
void rmq_init() {
Log[1] = 0;
for(int i = 2; i <= pc; ++i) Log[i] = Log[i >> 1] + 1;
for(int k = 1; 1 << k <= pc; ++k)
for(int i = 1; i + (1 << k) - 1 <= pc; ++i)
mi[i][k] = in[mi[i][k - 1]] < in[mi[i + (1 << k - 1)][k - 1]] ? mi[i][k - 1] : mi[i + (1 << k - 1)][k - 1];
}
int dLca(int l, int r) {
if(l == r) return dep[l];
l = pos[l], r = pos[r];
if(l > r) swap(l, r);
int k = Log[r - l + 1];
return in[mi[l][k]] < in[mi[r - (1 << k) + 1][k]] ? dep[mi[l][k]] : dep[mi[r - (1 << k) + 1][k]];
}
}
bool cmp(int a, int b) {
return Trie::in[a] < Trie::in[b];
}
int vt[N], head[N], st, ed, vc;
int pre1[N], pre2[N], suf1[N], suf2[N];
edge e[N * 20];
struct Heap {
int u, dis;
Heap(){}Heap(int u, int dis):u(u), dis(dis){}
bool operator <(const Heap &rhs) const {
return rhs.dis < dis;
}
};
priority_queue<Heap>Q;
int dis[N], vis[N], ans[N], from[N];
void dijk() {
fill(dis, dis + ndc + 1, inf);
fill(vis, vis + ndc + 1, 0);
dis[st] = 0;
Q.push(Heap(st, 0));
while(!Q.empty()) {
int u = Q.top().u; Q.pop();
if(vis[u]) continue;vis[u] = 1;
go(u)if(Min(dis[v], dis[u] + e[i].c + c[v])) {
Q.push(Heap(v, dis[v]));
from[v] = u;
}
}
fill(ans, ans + ndc + 1, inf);
for(int i = 1; i <= m; ++i) Min(ans[b[i]], dis[i]);
rep(i, 2, n) printf("%d
", ans[i]);
}
void Add(int a, int b, int c) {
e[++edc] = edge(head[a], b, c), head[a] = edc;
}
void prepare(int u) {
vc = 0;
for(auto v:A[u]) vt[++vc] = d[v];
for(auto v:B[u]) vt[++vc] = d[v];
sort(vt + 1, vt + 1 + vc, cmp);
vc = unique(vt + 1, vt + 1 + vc) - vt - 1;
rep(i, 1, vc) pre1[i] = ++ndc;
rep(i, 1, vc) pre2[i] = ++ndc, Add(pre1[i], pre2[i], Trie::dep[vt[i]]);
rep(i, 1, vc) suf1[i] = ++ndc;
rep(i, 1, vc) suf2[i] = ++ndc, Add(suf1[i], suf2[i], Trie::dep[vt[i]]);
for(auto v:A[u]) {
int p = lower_bound(vt + 1, vt + 1 + vc, d[v], cmp) - vt;
Add(v, pre1[p], 0);
Add(v, suf1[p], 0);
}
for(auto v:B[u]) {
int p = lower_bound(vt + 1, vt + 1 + vc, d[v], cmp) - vt;
Add(pre2[p], v, 0);
Add(suf2[p], v, 0);
}
rep(i, 1, vc - 1) {
Add(pre1[i], pre1[i + 1], 0);
Add(pre2[i], pre2[i + 1], 0);
Add(pre1[i], pre2[i + 1], Trie::dLca(vt[i], vt[i + 1]));
}
for(int i = vc; i >= 2; --i) {
Add(suf1[i], suf1[i - 1], 0);
Add(suf2[i], suf2[i - 1], 0);
Add(suf1[i], suf2[i - 1], Trie::dLca(vt[i], vt[i - 1]));
}
}
int main() {
T = gi();
while(T--) {
n = gi(), m = gi(), k = gi();
ndc = m;
Trie::edc = edc = 0;
Trie::tim = Trie::pc = 0;
fill(Trie::head, Trie::head + k + 1, 0);
re(head);
rep(i, 1, n) A[i].clear(), B[i].clear();
rep(i, 1, m) {
a[i] = gi(), b[i] = gi(), c[i] = gi(), d[i] = gi();
A[b[i]].pb(i);
B[a[i]].pb(i);
}
rep(i, 1, k - 1) {
int u = gi(), v = gi(), w = gi();
Trie::Add(u, v);
}
Trie::dfs(1);
Trie::rmq_init();
rep(i, 1, n) prepare(i);
st = ++ndc;
for(auto v:B[1]) Add(st, v, 0);
dijk();
fill(c, c + ndc + 1, 0);
}
return 0;
}