建立新图，原图中每条边在新图中是点，点权为$w_i$，边权为两个字符串的LCP。
对字典树进行DFS，将每个点周围一圈边对应的字符串按DFS序从小到大排序。
根据后缀数组利用height数组求LCP的原理，类似地可以得到：
令$h_i=LCP(str_i,str_{i+1})$，则$LCP(str_l,str_r)=\min(h_{l..r-1})$。
枚举每个$h_i$作为分界线，那么新图中两侧的点均可以通过不超过$h_i$的代价互相访问。
建立一排前缀虚点和后缀虚点然后对应前后缀之间连边即可。
如此建图的点数和边数均为$O(m)$，时间复杂度$O(m\log m)$。
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int>P;
const int N=50010,inf=~0U>>1;
int Case,n,m,K,i,j,x,y,z,g[N],nxt[N],size[N],f[N],d[N],son[N],loc[N],top[N],dfn;
int gi[N],go[N],V[N<<1],NXT[N<<1],ED;
int cnt,pi[N<<1],po[N<<1],si[N<<1],so[N<<1],cq,q[N<<1];
inline void read(int&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}
struct E{int a,b,c,d;}e[N];
namespace G{
const int N=450010,M=800010;
int g[N],v[M],w[M],nxt[M],ed,val[N],d[N];priority_queue<P,vector<P>,greater<P> >q;
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
inline void ext(int x,int y){
y+=val[x];
if(y<d[x])q.push(P(d[x]=y,x));
}
void solve(){
for(i=1;i<=cnt;i++)d[i]=inf;
for(i=1;i<=m;i++)if(e[i].a==1)ext(i,0);
while(!q.empty()){
P t=q.top();q.pop();
if(d[t.second]>t.first)continue;
for(i=g[t.second];i;i=nxt[i])ext(v[i],t.first+w[i]);
}
}
}
inline bool cmp(int x,int y){return loc[e[abs(x)].d]<loc[e[abs(y)].d];}
inline void add(int x,int y){nxt[y]=g[x];g[x]=y;}
inline void ADD(int&x,int y){V[++ED]=y;NXT[ED]=x;x=ED;}
void dfs(int x){
size[x]=1;
for(int i=g[x];i;i=nxt[i]){
f[i]=x,d[i]=d[x]+1;
dfs(i),size[x]+=size[i];
if(size[i]>size[son[x]])son[x]=i;
}
}
void dfs2(int x,int y){
loc[x]=++dfn;top[x]=y;
if(son[x])dfs2(son[x],y);
for(int i=g[x];i;i=nxt[i])if(i!=son[x])dfs2(i,i);
}
inline int lca(int x,int y){
for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]])swap(x,y);
return min(d[x],d[y]);
}
inline void solve(int x){
int i;
if(!gi[x]||!go[x])return;
cq=0;
for(i=gi[x];i;i=NXT[i])q[++cq]=V[i];
for(i=go[x];i;i=NXT[i])q[++cq]=-V[i];
sort(q+1,q+cq+1,cmp);
for(i=1;i<=cq;i++){
pi[i]=++cnt;
si[i]=++cnt;
po[i]=++cnt;
so[i]=++cnt;
if(i>1){
G::add(pi[i-1],pi[i],0);
G::add(po[i-1],po[i],0);
G::add(si[i],si[i-1],0);
G::add(so[i],so[i-1],0);
}
if(q[i]>0)G::add(q[i],pi[i],0),G::add(q[i],si[i],0);
else q[i]*=-1,G::add(po[i],q[i],0),G::add(so[i],q[i],0);
}
for(i=1;i<cq;i++){
int t=lca(e[q[i]].d,e[q[i+1]].d);
G::add(pi[i],po[i+1],t);
G::add(si[i+1],so[i],t);
}
}
int main(){
read(Case);
while(Case--){
read(n),read(m),read(K);
for(i=1;i<=m;i++){
read(e[i].a),read(e[i].b),read(e[i].c),read(e[i].d);
ADD(gi[e[i].b],i),ADD(go[e[i].a],i);
G::val[i]=e[i].c;
}
cnt=m;
for(i=1;i<K;i++)read(x),read(y),read(z),add(x,y);
dfs(1),dfs2(1,1);
for(i=1;i<=n;i++)solve(i);
G::solve();
for(i=2;i<=n;i++){
x=inf;
for(j=gi[i];j;j=NXT[j])x=min(x,G::d[V[j]]);
printf("%d\n",x);
}
for(i=1;i<=cnt;i++)G::g[i]=G::val[i]=0;
for(i=1;i<=K;i++)g[i]=size[i]=f[i]=d[i]=son[i]=0;
for(i=1;i<=n;i++)gi[i]=go[i]=0;
ED=dfn=G::ed=0;
}
return 0;
}
原文：http://www.cnblogs.com/clrs97/p/7833797.html