P2934 解题报告

· · 题解

前言

某模拟赛中打到的，场上切了，感觉还挺有趣的？

思路分析

这个题目操作是封住最后一条边，而给的限制条件也很奇怪：特别地，保证 1 到任何一个点 i 的最短路都是唯一的。

最后一条边不好考虑，我们考虑从限制条件下手。

这个限制条件告诉我们，如果我们只保留最短路会走过的边，那么剩下的就是一颗树。

因为路径唯一，所以最后一条边也唯一，推一下也就是对于每个点他的父亲唯一，那么显然就是一个树的形状。

考虑用 dijkstra 求出最短路的同时处理出最短路树。

这样第一步就完成了，我们有了一颗最短路树，接下来按照题目的要求要封住最后一条边球最短路。

显然大力的方法会 T 飞，考虑优化。

考虑我们已经求出 1 到点 i 的距离数组 d_i。

假设我们要求的点为 x，目前有条边 u\rightarrow v 边权为 w 且 v 在 x 子树里，那么经过这条边到 x 这条边的路径长度即为 d_u+w+d_v-d_x。

因为对于每条边，他的 d_u+w+d_v 是固定的，而对于每个点，他的 d_x 是固定的，所以说一个点的答案最多被一条边更新一次即可。

显然的是考虑先用 d_u+w+d_v 小的边更新点的答案，所以先按照这个值对于所有非树边排序。

然后考虑更新过程如何做到让一个点最多被更新一次。

想到并查集，对于一个点，更新他后把他合进父亲中即可。

显然，这题树剖也可以做，做法类似于其结合 MST 时的做法，在此不多赘述，读者可以自行思考一二（其实是我考场懒得码就上并查集了）。

Tips：题目有无解，无解输出 -1。

代码

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define int long long
using namespace std;
const int N=200010,p=338651,INF=0x3f3f3f3f3f3f3f3f;
struct edge{int v,w,id;};
struct node{int u,v,w;};
int n,m,cnt;bool mp[N];
int bcu[N<<1],bcv[N<<1],bcw[N<<1],a[N],d[N],ans[N],fa[N],dep[N];
vector<int>e[N];vector<edge>g[N];vector<node>eg;
namespace Fast_IO
{
    static char buf[1000000],*paa=buf,*pd=buf;
    #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
    inline int read()
    {
        int x(0),t(1);char fc(getchar());
        while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
        while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
        return x*t;
    }
    inline void print(int x)
    {
        if(x<0) putchar('-'),x=-x;
        if(x>9) print(x/10);
        putchar(x%10+'0');
    }
}
using namespace Fast_IO;
void dij()
{
    priority_queue<pair<int,int>>q;q.push(make_pair(0,1));memset(d,0x3f,sizeof d);d[1]=0;
    while(!q.empty())
    {
        int u=q.top().second;if(d[u]<-q.top().first){q.pop();continue;}q.pop();dep[u]=dep[fa[u]]+1;
        for(auto to:g[u])
        {
            int v=to.v,w=to.w;
            if(d[u]+w<d[v])
            {
                d[v]=d[u]+w;mp[a[v]]=0;
                q.push(make_pair(-d[v],v));fa[v]=u;
            }
        }
    }
}
inline void add(int u,int v) { e[u].emplace_back(v),e[v].emplace_back(u); }
struct DSU
{
    vector<int> h;
    inline void init(int n){h=vector<int>(n+10);for(int i=1;i<=n;i++) h[i]=i;}
    inline int find(int x){return h[x]==x?x:h[x]=find(h[x]);}
}f;
bool cmp(node x,node y){return d[x.u]+d[x.v]+x.w<d[y.u]+d[y.v]+y.w;}
signed main()
{
    n=read(),m=read();
    for(int i=1,u,v,w;i<=m;i++) bcu[i]=u=read(),bcv[i]=v=read(),bcw[i]=w=read(),g[u].emplace_back((edge){v,w,i}),g[v].emplace_back((edge){u,w,i});
    dij();memset(ans,-1,sizeof ans);
    for(int i=1;i<=m;i++) if(fa[bcu[i]]!=bcv[i]&&fa[bcv[i]]!=bcu[i]) eg.emplace_back((node){bcu[i],bcv[i],bcw[i]});
    sort(eg.begin(),eg.end(),cmp);f.init(n);
    for(auto i:eg)
    {
        int u=f.find(i.u),v=f.find(i.v);
        while(u!=v)
        {
            if(dep[u]<dep[v]) swap(u,v);
            ans[u]=d[i.u]+d[i.v]+i.w-d[u];
            f.h[u]=fa[u];u=f.find(u);
        }
    }
    for(int i=2;i<=n;i++) print(ans[i]),puts("");
    return 0;
}