最短路树+树上操作
最短路树是什么？如果1号点到任意节点的最短路唯一，那么边集组成的图就是一棵树。节点的深度就是到根节点（1号点）的最短路。这道题为什么要用到最短路树？因为我们不能经过最短路上的最后一条边，所以我们应该至少走一条非树边。什么样的非树边是合法的？假设我们要走到 i ，那么合法的边为：两个端点一个在子树中，一个不再子树中。也就是说对于一条非树边的两个端点a，b，她们能产生的贡献就是a - > lca , lca - >b (不包括lca，画画图就知道了)。那么我们就可以跑一遍dij，记录每个点在最短路上的前驱，之后建树。至于树上操作只需要区间修改，单点查询最大值，保证1操作在2操作后。那么这就可以用并查集实现了。（但是我写了树链剖分，惨遭卡常）
code
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#define half (l+r)>>1;
#include<ctime>
using namespace std;
const int maxn=100006;
int head[maxn*4],d[maxn],bhead[maxn],cur,son[maxn],id[maxn],top[maxn],fa[maxn],dis[maxn],size[maxn];
int n,m,cur2;
struct hzw
{
int to,next,v;
}tu[maxn*4],e[maxn*4];
struct zmd
{
int mx,lc,rc,tag;
}t[400006];
inline void add1(int a,int b,int c)
{
tu[cur].to=b;
tu[cur].next=bhead[a];
tu[cur].v=c;
bhead[a]=cur++;
}
inline void add2(int a,int b,int c)
{
e[cur2].to=b;
e[cur2].next=head[a];
e[cur2].v=c;
head[a]=cur2++;
}
inline int read(){
int x = 0;
char c = ' ';
while(c > '9' || c < '0') c = getchar();
while(c >= '0' && c <= '9'){
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
typedef pair<int ,int>p;
int last[maxn],vlast[maxn];
inline void dij()
{
priority_queue<p,vector<p>,greater<p> >q;
memset(dis,0x3f,sizeof(dis));
q.push(p(0,1));
dis[1]=0;
while (!q.empty())
{
p shit=q.top();
q.pop();
int s=shit.second;
if (shit.first>dis[s]) continue;
for (int i=bhead[s];i!=-1;i=tu[i].next)
{
int vv=tu[i].to;
if (dis[vv]>dis[s]+tu[i].v)
{
dis[vv]=dis[s]+tu[i].v;
last[vv]=s;
vlast[vv]=tu[i].v;
q.push(p(dis[vv],vv));
}
}
}
}
int cnt;
inline void build(int s,int l,int r)
{
t[s].tag=0x3f3f3f3f;
if (l==r)
{
t[s].mx=0x3f3f3f3f;
return;
}
int mid=half;
t[s].lc=++cnt;
build(cnt,l,mid);
t[s].rc=++cnt;
build(cnt,mid+1,r);
}
inline void pushdown(int s)
{
int ll=t[s].lc,rr=t[s].rc,zz=t[s].tag;
t[ll].mx=min(t[ll].mx,zz),t[rr].mx=min(t[rr].mx,zz);
t[ll].tag=min(t[ll].tag,zz),t[rr].tag=min(t[rr].tag,zz);
t[s].tag=0x3f3f3f3f;
}
inline void update(int s,int l,int r,int cl,int cr,int x)
{
if (cr<cl) return;
if (l==cl&&r==cr)
{
t[s].mx=min(t[s].mx,x);
t[s].tag=min(t[s].tag,x);
return;
}
if (t[s].tag<0x3f3f3f3f) pushdown(s);
int mid=half;
if (cr<=mid) update(t[s].lc,l,mid,cl,cr,x);
else if (cl>mid) update(t[s].rc,mid+1,r,cl,cr,x);
else
{
update(t[s].lc,l,mid,cl,mid,x);
update(t[s].rc,mid+1,r,mid+1,cr,x);
}
t[s].mx=min(t[t[s].lc].mx,t[t[s].rc].mx);
}
inline int query(int s,int l,int r,int p)
{
if(l==p&&r==p)
{
return t[s].mx;
}
if (t[s].tag<0x3f3f3f3f) pushdown(s);
int mid=half;
if (p<=mid) return query(t[s].lc,l,mid,p);
else return query(t[s].rc,mid+1,r,p);
}
bool vis[maxn];
inline int dfs1(int s,int f)
{
int maxson=0;
fa[s]=f;
size[s]=1;
for (int i=head[s];i!=-1;i=e[i].next)
{
if (e[i].to==f) continue;
d[e[i].to]=d[s]+e[i].v;
size[s]+=dfs1(e[i].to,s);
if (size[e[i].to]>maxson)
{
maxson=size[s];
son[s]=e[i].to;
}
}
return size[s];
}
int tot;
inline void dfs2(int s,int firs)
{
top[s]=firs;
id[s]=++tot;
if (!son[s]) return;
dfs2(son[s],firs);
for (int i=head[s];i!=-1;i=e[i].next)
{
if (id[e[i].to]) continue;
dfs2(e[i].to,e[i].to);
}
}
inline int lca(int x,int y)
{
if (x==y) return x;
while (top[x]!=top[y])
{
if (d[top[x]]<d[top[y]]) swap(x,y);
x=fa[top[x]];
}
if (d[x]>d[y]) swap(x,y);
return x;
}
inline void solve(int x,int y,int k,int num)
{
while (top[x]!=top[y])
{
if (d[top[x]]<d[top[y]]) swap(x,y);
int tmp=top[x]==k?id[top[x]]+1:id[top[x]];
update(1,1,n,tmp,id[x],num);
x=fa[x];
}
if (d[x]>d[y]) swap(x,y);
int tmp=x==k?id[x]+1:id[x];
update(1,1,n,tmp,id[y],num);
}
int main()
{
memset(bhead,-1,sizeof(bhead));
memset(head,-1,sizeof(head));
cnt=1;
n=read(),m=read();
for (int i=1,a,b,c;i<=m;++i)
{
a=read(),b=read(),c=read();
add1(a,b,c);
add1(b,a,c);
}
dij();
for (int i=2;i<=n;++i)
{
if (last[i]) add2(last[i],i,vlast[i]),add2(i,last[i],vlast[i]);
}
dfs1(1,1);
dfs2(1,1);
build(1,1,n);
for (int i=1;i<=n;++i)
{
if (dis[i]>0x3f3f3f3f-1) continue;
for (int j=bhead[i];j!=-1;j=tu[j].next)
{
int vv=tu[j].to,val=tu[j].v;
if (vv==fa[i]||i==fa[vv]) continue;
solve(i,vv,lca(i,vv),d[i]+d[vv]+val);
}
}
for (int i=2;i<=n;++i)
{
if (!id[i]) printf("-1
");
else
{
int tmp=query(1,1,n,id[i]);
if (tmp==0x3f3f3f3f) printf("-1
");
else printf("%d
",tmp-d[i]);
}
}
return 0;
}
收获：
1、关于最短路唯一的条件要想到最短路树
2、注意dij跑完建树的实现形式