题解：P13856 [CERC 2023] Labelled Paths

· · 题解

板子题，喵了。

这题可以加强为 任意两点求最短路，是等价的。

首先你需要发现一个事实：

A<B\Leftrightarrow C+A<C+B

但是！

A<B\not\Leftrightarrow A+C<B+C

其中 A,B,C 是字符串，+ 是顺序拼接，< 是字典序比较。

所以这题你 必须倒着做 求最短路，此时字典序才是最小的。

建反图，接下来你要对 每个原来的终点，在反图上走拓扑序，进行 \mathcal{O}(m) 次比较若干个串拼接在一起的大小。

比较若干个串拼接在一起的大小，相当于求两个拼接串的 LCP。

显然可以对每一段单独考虑。

就是 (l_1,r_1),(l_2,r_2),\cdots 和 (L_1,R_1),(L_2,R_2),\cdots 求 LCP。

显然先求 (l_1,r_1),(L_1,R_1)，然后删掉 LCP 继续做，直到当且第一位不相等。

总共最多比较 \mathcal{O}(n) 次。

比较一组相当于求后缀 LCP，和最后和两个长度取 \min。

于是假设求一次两个后缀的 LCP 的复杂度为 T(d)，则总复杂度为 \mathcal{O}(n^2mT(d))。

使用 SA+RMQ 做到 T(d)=\mathcal{O}(1)，使用二分哈希做到 T(d)=\mathcal{O}(\log d)。

我写了 SA，总复杂度 \mathcal{O}(d\log d+n^2m)，随便过。

::::info[\mathbf{code}]

#include<bits/stdc++.h>
#define LL long long
#define vec vector<pair<int,int>>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e6+5,M=605;
int n,m,L,S,a[N],pre[M];bool v[M];
vec f[M];basic_string<int>p;
vector<pair<int,pair<int,int>>>E[M];
string C;
int sa[N],rk[N],ht[N],mn[21][N];
inline int lcp(int x,int y)
{
    if(x==y) return L-x+1;x=rk[x],y=rk[y];
    if(x>y) swap(x,y);int t=__lg(y-(x++));
    return min(mn[t][x],mn[t][y-(1<<t)+1]);
}
inline void SA()
{
    static int _[N],c[N];int n=L,V=26;

    for(int i=1;i<=n;i++) c[a[i]=rk[i]=C[i-1]-'a'+1]++,sa[i]=i;
    for(int i=1;i<=V;i++) c[i]+=c[i-1];
    for(int i=n;i;i--) sa[c[rk[i]]--]=i;
    for(int w=1,t=0;w<n;w<<=1,V=t,t=0)
    {
        for(int i=n-w+1;i<=n;i++) _[++t]=i;
        for(int i=1;i<=n;i++) if(sa[i]>w) _[++t]=sa[i]-w;
        fill(c+1,c+1+V,0);
        for(int i=1;i<=n;i++) c[rk[i]]++;
        for(int i=1;i<=V;i++) c[i]+=c[i-1];
        for(int i=n;i;i--) sa[c[rk[_[i]]]--]=_[i];
        memcpy(_,rk,(n+1)<<2);t=0;
        auto eq=[&](int x,int y){return _[x]==_[y]&&_[x+w]==_[y+w];};
        for(int i=1;i<=n;i++) rk[sa[i]]=eq(sa[i-1],sa[i])?t:++t;
        if(t==n) break;
    }
    for(int i=1,k=0;i<=n;i++)
    {
        if(k) k--;
        while(a[i+k]==a[sa[rk[i]-1]+k]) k++;
        ht[rk[i]]=k;
    }memcpy(mn[0],ht,(n+1)<<2);
    for(int i=1;(1<<i)<=n;i++) for(int j=1;j+(1<<i)-1<=n;j++)
        mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
}
inline bool cmp(vec A,vec B)// A<B?
{
    while(1)
    {
        while(A.size()&&!A.back().second) A.pop_back();
        if(!A.size()) break;
        while(B.size()&&!B.back().second) B.pop_back();
        if(!B.size()) break;
        auto &[x,c]=A.back();auto &[y,d]=B.back();
        int L=min({lcp(x,y),c,d});
        x+=L,y+=L,c-=L,d-=L;
        if(c&&d) return a[x]<a[y];
    }
    return B.empty()?0:A.empty();
}
void dfs(int x){
    v[x]=1;
    for(auto [u,_]:E[x]) if(!v[u]) dfs(u);p+=x;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);cin>>n>>m>>L>>S>>C;SA();
    for(int u,v,l,d;m--;) cin>>u>>v>>l>>d,E[v].push_back({u,{l,d}});
    for(int u=1;u<=n;u++)
    {
        if(u==S){cout<<"1 "<<S<<"\n";continue;}
        for(int i=1;i<=n;i++) f[i].clear(),pre[i]=0;
        p.clear();fill_n(v+1,n,0);
        dfs(u);reverse(p.begin(),p.end());
        for(int i:p)
        {
            for(auto [j,w]:E[i])
            {
                vec t=f[i];t.push_back(w);
                if(f[j].empty()||cmp(t,f[j])) swap(f[j],t),pre[j]=i;
            }
        }
        if(!f[S].size()){cout<<"0\n";continue;}
        basic_string<int>g;for(int i=S;i;i=pre[i]) g+=i;
        cout<<g.size()<<" ";for(int i:g) cout<<i<<" ";cout<<"\n";
    }
    return 0;
}

::::