Define the construction of a tree so that any node x, dis(root,x) = which does not belong to the root goes to the shortest path of X.
Construction: Maintain which point and which side of each point is updated while running dijkstra. This side of the point is its father/father on the shortest path tree.
Example:
T1.bzoj3694 Shortest Path
Meaning: Given the shortest path tree, the shortest path from the last side of the tree to point i is not required.
Obviously, the path to a point must be through a non-tree edge, so consider what contribution each non-tree edge will make: assuming a non-tree edge (u,v) weight w, we can find that for any u,v path except LCA point x, assuming that x is on u to lca, its ans can be updated with dis(v)+w+dis(u)-dis(x). The final consideration of the item with X is to take the obvious vigorous tree with min. It can be cut.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+100;
const ll inf=1e18;
template<class T>
void rd(T &x)
{
char c=getchar();x=0;bool f=0;
while(!isdigit(c))f|=(c=='-'),c=getchar();
while(isdigit(c))x=x*10+c-48,c=getchar();
if(f)x=-x;
}
void Mn(ll &x,ll y)
{x=min(x,y);}
int bg[N],ed[N],val[N],num=0;
int n,m,hd[N],to[N],w[N],nxt[N],tot=-1;
int fa[N],son[N],dfn[N],top[N],dep[N],sz[N],tim=0;
ll dis[N],seg[N<<2],laz[N<<2];
void add(int x,int y,int z)
{
nxt[++tot]=hd[x],to[tot]=y,w[tot]=z,hd[x]=tot;
nxt[++tot]=hd[y],to[tot]=x,w[tot]=z,hd[y]=tot;
}
void dfs0(int x,int f)
{
fa[x]=f,sz[x]=1,son[x]=0;
for(int i=hd[x],v;~i;i=nxt[i])
{
v=to[i];
if(v==f)continue;
dep[v]=dep[x]+1,dis[v]=dis[x]+w[i],dfs0(v,x),sz[x]+=sz[v];
if(sz[v]>sz[son[x]])son[x]=v;
}
}
void dfs1(int x,int tp)
{
dfn[x]=++tim,top[x]=tp;
if(son[x])
{
dfs1(son[x],tp);
for(int i=hd[x],v;~i;i=nxt[i])
{
v=to[i];
if(v==fa[x]||v==son[x])continue;
dfs1(v,v);
}
}
}
int get_lca(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
x=fa[fx],fx=top[x];
}
return dep[x]<dep[y]?x:y;
}
void push_down(int k)
{
if(laz[k]<inf)
{
Mn(seg[k<<1],laz[k]),Mn(laz[k<<1],laz[k]);
Mn(seg[k<<1|1],laz[k]),Mn(laz[k<<1|1],laz[k]);
laz[k]=inf;
}
}
void upd(int L,int R,int l,int r,int k,ll x)
{
//cerr<<l<<' '<<r<<' '<<k<<'\n';
if(L<=l&&r<=R)
{
Mn(seg[k],x);
Mn(laz[k],x);
return;
}
int mid=(l+r)>>1;
push_down(k);
if(L<=mid)upd(L,R,l,mid,k<<1,x);
if(R>mid)upd(L,R,mid+1,r,k<<1|1,x);
}
void cg(int x,int y,ll z)
{
int fx=top[x],fy=top[y];
//cerr<<fx<<' '<<fy<<'\n';
while(fx!=fy)
{
//cerr<<n<<'\n';
upd(dfn[fx],dfn[x],1,n,1,z);
x=fa[fx],fx=top[x];
}
if(x==y)return;
upd(dfn[y]+1,dfn[x],1,n,1,z);
}
ll qry(int to,int l,int r,int k)
{
if(l==r)return seg[k];
int mid=(l+r)>>1;
push_down(k);
if(to<=mid)return qry(to,l,mid,k<<1);
else return qry(to,mid+1,r,k<<1|1);
}
int main()
{
int x,y,z,op;
rd(n),rd(m);
memset(hd,-1,sizeof hd);
for(int i=1;i<=m;i++)
{
rd(x),rd(y),rd(z),rd(op);
if(op==1)add(x,y,z);
else bg[++num]=x,ed[num]=y,val[num]=z;
}
dep[1]=1,dfs0(1,0),dfs1(1,1);
memset(seg,63,sizeof seg);
memset(laz,63,sizeof laz);
for(int i=1,u,v,lca;i<=num;i++)
{
u=bg[i],v=ed[i];
if(dep[u]<dep[v])swap(u,v);
lca=get_lca(u,v);
//cerr<<u<<' '<<v<<' '<<lca<<'\n';
if(lca==v)cg(u,v,dis[u]+dis[v]+val[i]);
else cg(u,lca,dis[u]+dis[v]+val[i]),cg(v,lca,dis[u]+dis[v]+val[i]);
}
ll res;
for(int i=2;i<=n;i++)
{
res=qry(dfn[i],1,n,1);
if(res>=inf)printf("-1 ");
else printf("%lld ",res-dis[i]);
}
}T2.cf 1005F
The Scheme of Building Shortest Path Tree
It is not necessary to build the shortest path tree, because the edge weight is 1, so it is easy to do. bfs calculates the dis of each point, and then traverses all connected points for each point. if DIS is the current minus one, then it can certainly become the precursor of the current point, and throw into a vector, then the total scheme is the product of all points vector size, and the output scheme is dfs.
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define ll long long
using namespace std;
const int N=2e5+100;
const ll inf=1e18;
template<class T>
void rd(T &x)
{
char c=getchar();x=0;bool f=0;
while(!isdigit(c))f|=(c=='-'),c=getchar();
while(isdigit(c))x=x*10+c-48,c=getchar();
if(f)x=-x;
}
void Mn(ll &x,ll y)
{x=min(x,y);}
int n,m,k,dis[N],can;
bool vis[N];
vector<pii>mp[N],fr[N];
void P()
{
for(int i=1;i<=m;i++)
vis[i]?putchar('1'):putchar('0');
puts("");
}
void dfs(int x)
{
if(x>n)
{
P();
--can;
if(can==0)exit(0);
}
for(int i=0,v,wh;i<fr[x].size();i++)
{
v=fr[x][i].fi,wh=fr[x][i].sc;
vis[wh]=1,dfs(x+1),vis[wh]=0;
}
}
int main()
{
rd(n),rd(m),rd(k);
for(int i=1,u,v;i<=m;i++)
{
rd(u),rd(v);
mp[u].push_back(pii(v,i));
mp[v].push_back(pii(u,i));
}
int nw;
queue<int>q;
memset(dis,-1,sizeof dis);
dis[1]=0,q.push(1);
while(!q.empty())
{
nw=q.front(),q.pop();
for(int i=0,v;i<mp[nw].size();i++)
{
v=mp[nw][i].fi;
if(dis[v]==-1)dis[v]=dis[nw]+1,q.push(v);
}
}
for(int i=2;i<=n;i++)
{
for(int j=0,v;j<mp[i].size();j++)
{
v=mp[i][j].fi;
if(dis[v]+1==dis[i])fr[i].push_back(mp[i][j]);
}
}
can=1;
for(int i=2;i<=n;i++)
{
can*=fr[i].size();
can=min(can,k);
}
printf("%d\n",can);
dfs(2);
}T3.cf 1076D. Edge Deletion
Obviously, they are deleted one by one from the bottom of the shortest path tree.
#include<bits/stdc++.h>
#define pii pair<ll,int>
#define fi first
#define sc second
#define ll long long
using namespace std;
const int N=3e5+100;
const ll inf=1e18;
template<class T>
void rd(T &x)
{
char c=getchar();x=0;bool f=0;
while(!isdigit(c))f|=(c=='-'),c=getchar();
while(isdigit(c))x=x*10+c-48,c=getchar();
if(f)x=-x;
}
void Mn(ll &x,ll y)
{x=min(x,y);}
int n,m,k,hd[N],nxt[N*2],to[N*2],cost[N*2],idx[N*2],bf[N],tax[N],tot=-1;
ll dis[N];
bool kep[N];
void add(int x,int y,int z,int id)
{
nxt[++tot]=hd[x],idx[tot]=id,to[tot]=y,cost[tot]=z,hd[x]=tot;
nxt[++tot]=hd[y],idx[tot]=id,to[tot]=x,cost[tot]=z,hd[y]=tot;
}
void dij()
{
priority_queue<pii,vector<pii>,greater<pii> >pq;
int nw;ll d;
memset(dis,63,sizeof dis);
dis[1]=0,pq.push(pii(0,1));
while(!pq.empty())
{
nw=pq.top().sc,d=pq.top().fi,pq.pop();
if(dis[nw]<d)continue;
for(int i=hd[nw],v;~i;i=nxt[i])
{
v=to[i];
if(dis[v]>d+cost[i])
{
dis[v]=d+cost[i];
bf[v]=idx[i];
pq.push(pii(dis[v],v));
}
}
}
}
bool cmp(int x,int y)
{return dis[x]>dis[y];}
int main()
{
rd(n),rd(m),rd(k);
memset(hd,-1,sizeof hd);
for(int i=1,u,v,w;i<=m;i++)
{
//cerr<<i<<'\n';
rd(u),rd(v),rd(w);
add(u,v,w,i);
}
//cerr<<"!!"<<'\n';
dij();
for(int i=1;i<n;i++)
tax[i]=i+1,kep[bf[i+1]]=1;
sort(tax+1,tax+n,cmp);
int has=n-1,ps=1;
while(has>k)
{
kep[bf[tax[ps++]]]=0;
--has;
}
printf("%d\n",has);
for(int i=1;i<=m;i++)
if(kep[i])printf("%d ",i);
}