# ShanLunjiaJian的blog

### P3783 [SDOI2017]天才黑客 题解

posted on 2021-04-03 22:38:43 | under 题解 |

$$\mathrm{dep}(\mathrm{lca}(u,v))=\min_{i=id_u}^{id_v}d_i$$

code:

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
using std::priority_queue;
using std::sort;
using std::vector;

inline void swap(int &x,int &y){ x^=y^=x^=y; }
inline long long min(long long x,long long y){ return x<y?x:y; }

namespace Tree
{

struct Graph
{
struct Edge
{
int v,next;
}e[100002];
int ecnt,h[20002];
{
e[++ecnt]={v,h[u]};
h[u]=ecnt;
e[++ecnt]={u,h[v]};
h[v]=ecnt;
}
inline void clear()
{
ecnt=0;
memset(h,0,sizeof(h));
}
}G,T;

int f[20][40002],id[20002],cnt,dep[20002],lg[40002];

inline void cleartree()
{
G.clear(),T.clear();
cnt=0;
}

void predfs(int u,int _fa)
{
f[0][++cnt]=u,id[u]=cnt;
dep[u]=dep[_fa]+1;
for(int i=G.h[u];i;i=G.e[i].next)
if(G.e[i].v!=_fa)
predfs(G.e[i].v,u),f[0][++cnt]=u;
}

inline void st_init()
{
for(int k=1;k<=20;k++)
for(int i=1;i<=cnt-(1<<k)+1;i++)
f[k][i]=(dep[f[k-1][i]]<dep[f[k-1][i+(1<<(k-1))]]?f[k-1][i]:f[k-1][i+(1<<(k-1))]);
for(int i=2;i<=cnt;i++)
lg[i]=lg[i>>1]+1;
}

inline int lca(int u,int v)
{
u=id[u],v=id[v];
if(u>v) swap(u,v);
int l=lg[v-u+1];
return dep[f[l][u]]<dep[f[l][v-(1<<l)+1]]?f[l][u]:f[l][v-(1<<l)+1];
}

int s[20002],top;
inline void clear(int u){ T.h[u]=0; }
inline void insert(int u)
{
int l=lca(u,s[top]);
if(l!=s[top])
{
}
clear(u),s[++top]=u;
}

inline bool cmp(int u,int v){ return id[u]<id[v]; }
inline void build(int n,int *a)
{
sort(a+1,a+n+1,cmp);
T.ecnt=0,clear(1),s[top=1]=1;
for(int i=1;i<=n;i++)
if(a[i]!=1&&a[i]!=a[i-1]) insert(a[i]);
}

inline void get_dfn(int u,int _fa,int *dfn,int *id,int &cnt)
{
dfn[++cnt]=dep[u],id[u]=cnt;
for(int i=T.h[u];i;i=T.e[i].next)
if(T.e[i].v!=_fa)
get_dfn(T.e[i].v,u,dfn,id,cnt),dfn[++cnt]=dep[u];
}

}

int ncnt;
inline int new_node(){ return ++ncnt; }

int n,m,k;
int nodein[50002],nodeout[50002],prein[40002],sufin[40002],preout[40002],sufout[40002];
struct Pair{ int u,id; };
vector<Pair> in[50002],out[50002];

namespace Dij
{

struct Edge
{
int v,w,next;
}e[20000002];

int ecnt,h[2000002];
inline void add_edge(int u,int v,int w)
{
e[++ecnt]={v,w,h[u]};
h[u]=ecnt;
}

inline void clear()
{
ecnt=0;
memset(h,0,sizeof(h));
}

struct DijNode
{
int u;long long dis;
};
inline bool operator < (DijNode x,DijNode y){ return x.dis>y.dis; }

long long dis[2000002];
bool vis[2000002];

inline void Dij()
{
priority_queue<DijNode> q;
//while(!q.empty()) q.pop();
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
for(int i=0;i<out[1].size();i++)
dis[out[1][i].u]=0,q.push({out[1][i].u,0});
while(!q.empty())
{
int u=q.top().u;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=h[u];i;i=e[i].next)
if(dis[u]+e[i].w<dis[e[i].v])
dis[e[i].v]=dis[u]+e[i].w,q.push({e[i].v,dis[e[i].v]});
}
}

}

inline void build_graph()
{
static int temp[100002],dfn[40002],id[100002];
for(int u=1;u<=n;u++)
{
int tcnt=0;
for(int i=0;i<in[u].size();i++)
temp[++tcnt]=in[u][i].id;
for(int i=0;i<out[u].size();i++)
temp[++tcnt]=out[u][i].id;
Tree::build(tcnt,temp);
int cnt=0;
Tree::get_dfn(1,0,dfn,id,cnt);
for(int i=1;i<=cnt;i++)
prein[i]=new_node(),sufin[i]=new_node(),preout[i]=new_node(),sufout[i]=new_node();
for(int i=2;i<=cnt;i++)
for(int i=1;i<=cnt-1;i++)
for(int i=0;i<in[u].size();i++)
for(int i=0;i<out[u].size();i++)
for(int i=1;i<=cnt;i++)
}
}

int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1,u,v,w,id;i<=m;i++)
scanf("%d%d%d%d",&u,&v,&w,&id),
in[v].push_back({nodeout[i],id}),out[u].push_back({nodein[i],id});
for(int i=1,u,v,w;i<k;i++)
Tree::dep[0]=-1,Tree::predfs(1,0),Tree::st_init();
build_graph();
Dij::Dij();
for(int i=2;i<=n;i++)
{
long long ans=0x7fffffffffffffff;
for(int j=0;j<in[i].size();j++)
ans=min(ans,Dij::dis[in[i][j].u]);
printf("%lld\n",ans);
}
Dij::clear();
Tree::cleartree();
ncnt=0;
for(int i=1;i<=n;i++)
in[i].clear(),out[i].clear();
}
return 0;
}