Description
给出一个$n$个点$m$条边的无向图,$n$个点的编号从$1-n$,定义源点为$1$.
定义最短路树如下:从源点$1$经过边集$T$到任意一点$i$有且仅有一条路径,且这条路径是整个图$1$到$i$的最短路径,边集$T$构成最短路树.
给出最短路树,求对于除了源点$1$外的每个点$i$,求最短路,要求不经过给出的最短路树上的$1$到$i$的路径的最后一条边.
Input
第一行包含两个数$n$和$m$,表示图中有$n$个点和$m$条边.
接下来$m$行,每行有四个数$a_i,b_i,l_i,t_i$,表示图中第$i$条边连接$a_i$和$b_i$权值为$l_i,t_i$为$1$表示这条边是最短路树上的边,$t_i$为$0$表示不是最短路树上的边.
Output
输出$n-1$个数,第$i$个数表示从$1$到$i+1$的要求的最短路.无法到达输出$-1$.
Sample Input
5 9
3 1 3 1
1 4 2 1
2 1 6 0
2 3 4 0
5 2 3 0
3 2 2 1
5 3 1 1
3 5 2 0
4 5 4 0
Sample Output
6 7 8 5
HINT
$n;leq;4000,m;leq;100000，1;leq;l_i;leq;100000$
Solution
对于一条不在最短路树上的边$e[u][v]$,显然它只对$(u,v)$上除了$lca(u,v)$之外的点有影响.
对于$(lca(u,v),v)$上除了$lca(u,v)$之外的点$k$,一条可行路径为$1->u->v->k$.
($lca(u,v)$不合法,不属于$(u,v)$的点显然更劣.)
设$dis[i]$为最短路树中$(1,i)$的长度,
则这条可行路径$1->u->v->k$长度为$dis[u]+e[u][v]+dis[v]-dis[k]$.
$dis[k]$为定值,则要求合法的最小的$dis[u]+e[u][v]+dis[v]$.
这个可以用树链剖分+线段树维护.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 4005 #define M 100005 #define INF 900000000 using namespace std; struct linetree{ int l,r,m; }lt[M]; struct graph{ int nxt,to,w; }e[M<<1]; struct line{ int l,r,w; }a[M]; int g[N],dis[N],n,m,tot,cnt; int f[N],p[N],dep[N],siz[N],son[N],top[N]; inline void addedge(int x,int y,int w){ e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;e[cnt].w=w; } inline void dfs1(int u){ int m=0;siz[u]=1; for(int i=g[u];i;i=e[i].nxt) if(!dep[e[i].to]){ f[e[i].to]=u; dep[e[i].to]=dep[u]+1; dis[e[i].to]=dis[u]+e[i].w; dfs1(e[i].to); siz[u]+=siz[e[i].to]; if(siz[e[i].to]>m){ son[u]=e[i].to; m=siz[e[i].to]; } } } inline void dfs2(int u,int tp){ top[u]=tp;p[u]=++cnt; if(son[u]) dfs2(son[u],tp); for(int i=g[u];i;i=e[i].nxt) if(e[i].to!=f[u]&&e[i].to!=son[u]) dfs2(e[i].to,e[i].to); } inline void build(int u,int l,int r){ lt[u].l=l;lt[u].r=r;lt[u].m=INF; if(lt[u].l<lt[u].r){ int mid=(lt[u].l+lt[u].r)>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); } } inline void cover(int u,int l,int r,int k){ if(lt[u].l>=l&<[u].r<=r){ lt[u].m=min(lt[u].m,k); } else if(lt[u].l<lt[u].r){ int lef=u<<1,rig=u<<1|1; int mid=(lt[u].l+lt[u].r)>>1; lt[lef].m=min(lt[u].m,lt[lef].m); lt[rig].m=min(lt[u].m,lt[rig].m); if(l<=mid) cover(lef,l,r,k); if(r>mid) cover(rig,l,r,k); } } inline int ask(int u,int x){ if(lt[u].l<lt[u].r){ int lef=u<<1,rig=u<<1|1; int mid=(lt[u].l+lt[u].r)>>1; lt[lef].m=min(lt[u].m,lt[lef].m); lt[rig].m=min(lt[u].m,lt[rig].m); if(x<=mid) return ask(lef,x); return ask(rig,x); } return lt[u].m; } inline void cov(int u,int v,int k){ int t; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]){ t=u;u=v;v=t; } cover(1,p[top[u]],p[u],k); u=f[top[u]]; } if(p[u]>p[v]){ t=u;u=v;v=t; } if(u!=v) cover(1,p[u]+1,p[v],k); } inline void Aireen(){ scanf("%d%d",&n,&m); for(int i=1,j,k,w,t;i<=m;++i){ scanf("%d%d%d%d",&j,&k,&w,&t); if(t){ addedge(j,k,w);addedge(k,j,w); } else{ a[++tot].l=j;a[tot].r=k;a[tot].w=w; } } dep[1]=1;dfs1(1);cnt=0;dfs2(1,1); build(1,1,n);m=tot; for(int i=1;i<=m;++i) cov(a[i].l,a[i].r,a[i].w+dis[a[i].l]+dis[a[i].r]); for(int i=2,k;i<=n;++i){ k=ask(1,p[i]); if(k==INF) printf("-1 "); else printf("%d ",k-dis[i]); } } int main(){ freopen("dis.in","r",stdin); freopen("dis.out","w",stdout); Aireen(); fclose(stdin); fclose(stdout); return 0; }