题面
题解
去看\(shadowice\)巨巨写得前后缀优化建图吧
话说我似乎连线段树优化建图的做法都不会
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define pb push_back
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R ll x){
if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
int n,m,k,dfn[20005],dep[20005];
namespace Tr{
const int N=2e4+5;
struct eg{int v,nx;}e[N];int head[N],tot;
inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
int top[N],fa[N],sz[N],son[N],cnt;
void dfs1(int u){
sz[u]=1,dep[u]=dep[fa[u]]+1;
go(u)if(v!=fa[u]){
fa[v]=u,dfs1(v),sz[u]+=sz[v];
sz[v]>sz[son[u]]?son[u]=v:0;
}
}
void dfs2(int u,int t){
top[u]=t,dfn[u]=++cnt;
if(!son[u])return;
dfs2(son[u],t);
go(u)if(!top[v])dfs2(v,v);
}
inline int LCA(R int u,R int v){
while(top[u]!=top[v]){
dep[top[u]]<dep[top[v]]?(swap(u,v),0):0;
u=fa[top[u]];
}return dep[u]<dep[v]?u:v;
}
inline void init(){dep[0]=-1;dfs1(1),dfs2(1,1);}
inline void clr(){fp(i,1,k)head[i]=fa[i]=son[i]=top[i]=0;tot=cnt=0;}
}
namespace Gr{
const int N=5e4+5,V=(N<<2)+5,E=N*20+5;
struct eg{int v,nx,w;}e[E];int head[V],tot;
inline void add(R int u,R int v,R int w){e[++tot]={v,head[u],w},head[u]=tot;}
vector<int>eof[N],eif[N],eob[N],eib[N],tr;
int tp[V],S,cnt;
inline bool cmp(const int &x,const int &y){return dfn[tp[x]]<dfn[tp[y]];}
void ins(int u,int v,int w,int d){
u==1?(add(S,cnt+1,0),add(S,cnt+3,0),0):0,
tp[cnt+1]=tp[cnt+2]=tp[cnt+3]=tp[cnt+4]=d,
add(cnt+1,cnt+2,w),add(cnt+1,cnt+4,w),add(cnt+3,cnt+2,w),add(cnt+3,cnt+4,w),
eof[u].pb(++cnt),eif[v].pb(++cnt),eob[u].pb(++cnt),eib[v].pb(++cnt);
}
void build(){
fp(u,1,n){
sort(eof[u].begin(),eof[u].end(),cmp),
sort(eif[u].begin(),eif[u].end(),cmp),
sort(eob[u].begin(),eob[u].end(),cmp),
sort(eib[u].begin(),eib[u].end(),cmp);
fp(i,0,eof[u].size()-2)add(eof[u][i],eof[u][i+1],0);
fp(i,0,eif[u].size()-2)add(eif[u][i],eif[u][i+1],0);
fp(i,0,eob[u].size()-2)add(eob[u][i+1],eob[u][i],0);
fp(i,0,eib[u].size()-2)add(eib[u][i+1],eib[u][i],0);
tr.resize(eof[u].size()+eif[u].size());
int s1=eof[u].size(),s2=eib[u].size();
merge(eof[u].begin(),eof[u].end(),eif[u].begin(),eif[u].end(),tr.begin(),cmp);
for(R int t=0,i=0,j=0,s=tr.size()-1,w;t<s;++t){
tr[t]&1?++j:++i,w=dep[Tr::LCA(tp[tr[t]],tp[tr[t+1]])];
(i&&j!=s1)?(add(eif[u][i-1],eof[u][j],w),0):0,
(j&&i!=s2)?(add(eib[u][i],eob[u][j-1],w),0):0;
}
}
}
struct node{
int u;ll d;
node(){}
node(R int uu,R ll dd):u(uu),d(dd){}
inline bool operator <(const node &b)const{return d>b.d;}
};priority_queue<node>q;
int vis[V];ll dis[V];
void dijkstra(){
fp(i,1,cnt)dis[i]=(1ll<<60);
q.push(node(S,dis[S]=0));
int u;
while(!q.empty()){
u=q.top().u,q.pop();if(vis[u])continue;vis[u]=1;
go(u)cmin(dis[v],dis[u]+e[i].w)?(q.push(node(v,dis[v])),0):0;
}
fp(i,2,n){
ll res=(1ll<<60);
fp(j,0,eif[i].size()-1)cmin(res,dis[eif[i][j]]);
fp(j,0,eib[i].size()-1)cmin(res,dis[eib[i][j]]);
print(res);
}
}
void clr(){
fp(i,1,n){
vector<int>().swap(eof[i]),
vector<int>().swap(eif[i]),
vector<int>().swap(eob[i]),
vector<int>().swap(eib[i]);
}
fp(i,1,cnt+1)head[i]=vis[i]=0;
cnt=tot=0;
}
}
void solve(){
n=read(),m=read(),k=read(),Gr::S=(m<<2)+1;
for(R int i=1,u,v,w,d;i<=m;++i)u=read(),v=read(),w=read(),d=read(),Gr::ins(u,v,w,d);
for(R int i=1,u,v,w;i<k;++i)u=read(),v=read(),w=read(),Tr::add(u,v);
Tr::init(),Gr::build(),Gr::dijkstra();
}
int main(){
// freopen("testdata.in","r",stdin);
for(int T=read();T;--T)solve(),Tr::clr(),Gr::clr();
return Ot(),0;
}