题意

一个 \(n\) 点 \(m\) 边的有向图，还有一棵 \(k\) 个节点的 trie ，每条边上有一个字符串，可以用 trie 的根到某个节点的路径来表示。每经过一条边，当前携带的字符串就会变成边上的字符串，经过一条边的代价是边权+边上的字符串和当前字符串的 lcp，问从 1 号点走到所有点的最小代价。

\(n,m\le 50000, k\le 20000\)

分析

• 将边看成点，如果有 \(e1 \rightarrow x\rightarrow e2\) , 连边 \(e1 \rightarrow e2\) ，代价就是 lcp ，考虑优化建图。
• 实际本题的字典树是一个提示，可以将一个点的子节点按照字符大小遍历，根据后缀数组求 \(height\) 的性质容易知道两个点 \(u,v\) 的 lca 就是他们 dfs 序中间的所有相邻点的 lca 的深度最小的那一个
• 这个结论也可以通过点作为 lca 的依据（至少两个子树内有关键点）得到，也就是说一定可以通过这种方式表示出这两个点的lca。所以前缀后缀优化建图即可。
• 复杂度 \(O(nlogn)\) 。
• 注意可能出现一条出边一条入边的字符串相同的情况，所以每个前缀节点还要直接连向对应的后缀节点。

代码

#include
    
     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 
     
       inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}template 
      
        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
       
         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
        
         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\n", 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;}