先求最短路树。考虑每一条非树边(u,v,len)，设w=LCA(u,v)，这条边会对w->v上的点x(x!=w)有dis[u]+dis[v]-dis[x]+len的距离。
每条边用dis[u]+div[v]+len更新链。树剖就做完了。
因为每个点只需取最小值，所以把边按dis[u]+div[v]+len排序后并查集更新链也行。
复杂度(O(nalpha(n)+mlogm))。
树DP失败，好像没法处理子树内的ndis互相更新。。唉。
//12680kb 556ms
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mp std::make_pair
#define pr std::pair<int,int>
const int N=1e5+5,M=4e5+5,INF=0x3f3f3f3f;
int n,fa[N],ff[N],Enum,H[N],nxt[M],to[M],len[M],dis[N],ans[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Edge
{
int u,v,w;
bool operator <(const Edge &x)const{
return w<x.w;
}
}e[M];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AE(int w,int u,int v)//order
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
void Dijkstra()
{
static bool vis[N];
static std::priority_queue<pr> q;
memset(dis,0x3f,sizeof dis);
q.push(mp(dis[1]=0,1));
while(!q.empty())
{
int x=q.top().second; q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if(dis[v=to[i]]>dis[x]+len[i])
fa[v]=x, q.push(mp(-(dis[v]=dis[x]+len[i]),v));
}
}
inline int Find(int x)
{
return x==ff[x]?x:ff[x]=Find(ff[x]);
}
void Update(int u,int v,int val)
{
u=Find(u), v=Find(v);
while(u!=v)
{
if(dis[u]<dis[v]) std::swap(u,v);//没必要用dep，保证在一条链上时上下不颠倒就行了
ans[u]=val-dis[u];
u=ff[u]=Find(fa[u]);
}
}
int main()
{
n=read(), Enum=1;
for(int m=read(),i=1; i<=m; ++i) AE(read(),read(),read());
Dijkstra();
int t=0;
for(int i=2,lim=Enum; i<=lim; i+=2)
{
int u=to[i], v=to[i^1];
if(fa[u]==v||fa[v]==u) continue;
e[++t]=(Edge){u,v,dis[u]+dis[v]+len[i]};
}
std::sort(e+1,e+1+t);
for(int i=1; i<=n; ++i) ff[i]=i;
for(int i=1; i<=t; ++i) Update(e[i].u,e[i].v,e[i].w);
for(int i=2; i<=n; ++i) printf("%d
",ans[i]?ans[i]:-1);
return 0;
}
纪念一下10分的树DP
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define mp std::make_pair
#define pr std::pair<LL,int>
#define Vec std::vector<int>
typedef long long LL;
const int N=1e5+5,M=4e5+5;
const LL INF=0x3f3f3f3f3f3f3f3f;
int n,pre[N],dep[N],fa[N],sz[N],son[N],in[N],out[N],ref[N],Index,top[N];
LL dis[N],ndis[N],ans[N];
bool is_t[M];
Vec vec[N];
bool de;
struct Graph
{
int Enum,H[N],nxt[M],fr[M],to[M];
LL len[M];
inline void AE(int w,int u,int v)//order
{
to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
inline void AE_d(int u,int v,LL w)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
}
}T,G;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Dijkstra()
{
static bool vis[N];
static std::priority_queue<pr> q;
memset(dis,0x3f,sizeof dis);
q.push(mp(dis[1]=0,1));
while(!q.empty())
{
int x=q.top().second; q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=G.H[x],v; i; i=G.nxt[i])
if(dis[v=G.to[i]]>dis[x]+G.len[i])
pre[v]=i, q.push(mp(-(dis[v]=dis[x]+G.len[i]),v));
}
for(int i=2; i<=n; ++i) is_t[pre[i]]=1, T.AE_d(G.fr[pre[i]],i,G.len[pre[i]]);
}
void DFS1(int x)
{
int mx=0; sz[x]=1;
for(int i=T.H[x],v; i; i=T.nxt[i])
{
fa[v=T.to[i]]=x, dep[v]=dep[x]+1, DFS1(v), sz[x]+=sz[v];
if(sz[v]>mx) mx=sz[v], son[x]=v;
}
}
void DFS2(int x,int tp)
{
ref[in[x]=++Index]=x, top[x]=tp;
if(son[x])
{
DFS2(son[x],tp);
for(int i=T.H[x]; i; i=T.nxt[i])
if(T.to[i]!=son[x]) DFS2(T.to[i],T.to[i]);
}
out[x]=Index;
}
inline int LCA(int u,int v)
{
while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
return dep[u]>dep[v]?v:u;
}
inline int LCA2(int u,int lca)
{
int las=u;
while(top[u]!=top[lca]) u=fa[las=top[u]];
return u==lca?las:ref[in[lca]+1];
}
LL Solve(int x)
{
if(de) printf("
Begin!
ans[%d]=%I64d
",x,ans[x]);
for(int i=G.H[x],v; i; i=G.nxt[i])
if((v=G.to[i])!=fa[x]&&(in[v=G.to[i]]<in[x]||out[v]>out[x]))
de&&(printf("ans:%d->%d:%I64d
",v,x,dis[v]+G.len[i])),
ans[x]=std::min(ans[x],dis[v]+G.len[i]);
if(de) printf("update by other tree:ans[%d]=%I64d
",x,ans[x]);
for(int i=0,l=vec[x].size(); i<l; ++i)
{
int id=vec[x][i],u=G.fr[id],v=G.to[id];
de&&(printf("ndis:%d->%d:%I64d
",u,v,dis[u]+G.len[id]));
ndis[v]=std::min(ndis[v],dis[u]+G.len[id]);
}
LL mn=INF;
for(int i=T.H[x],v; i; i=T.nxt[i])
mn=std::min(mn,Solve(T.to[i])+T.len[i]);
ndis[x]=std::min(ndis[x],mn), ans[x]=std::min(ans[x],ndis[x]);
if(de) printf("End ans[%d]=%I64d ndis[%d]=%I64d mn=%I64d
",x,ans[x],x,ndis[x],mn);
return ndis[x];
}
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
n=read(), G.Enum=1;
for(int m=read(),i=1; i<=m; ++i) G.AE(read(),read(),read());
Dijkstra(), DFS1(1), DFS2(1,1);
de=0;
if(de) for(int i=1; i<=n; ++i) printf("%d:fa:%d in:%d out:%d top:%d
",i,fa[i],in[i],out[i],top[i]);
for(int i=2,lim=G.Enum; i<=lim; ++i)
{
if(is_t[i]||is_t[i^1]) continue;
int u=G.fr[i], v=G.to[i], w=LCA(u,v), w2=LCA2(v,w);
// printf("LCA2(%d,%d):%d
",u,v,w2);
vec[w2].push_back(i);
}
memset(ans,0x3f,sizeof ans);
memset(ndis,0x3f,sizeof ndis);
Solve(1);
for(int i=2; i<=n; ++i) printf("%I64d
",ans[i]==INF?-1ll:ans[i]);
return 0;
}