题解 [模拟赛 2024.1.24] 乱斗之星

· · 个人记录

首先可以注意到我们只需考虑 T = 1, T_{\max}：因为任意一条路径的花费都可以表示为常数或一个关于 T 的一次函数，则其只能在两个端点处取得最值。

然后问题转化为一个 |V| = O(n), |E| = O(n^2) 的最短路。

测试点 13 \sim 20：m = n - 1 即原图为一棵树

考虑用一个优先队列维护目前可以用来更新的 (i, ans_i + c_i)，我们每次取出最小者尝试更新每个 j。

然后就有一个劣质的 2log 树剖 + 平衡树做法（

对于树上路径问题，考虑建出点分树，则对于点分树上 i 到根的路径上的一个分治中心 r，我们可以更新 dis(i, r) + dis(r, j) \leq f_i 的 j。

考虑对每个分治中心把 j 按 dis(r, j) 排序，则我们每次移动指针更新这一轮的 j 即可。

时间复杂度为 O(n \log n)。

无特殊限制

首先跑出原图的一棵生成树。

如果只经过树边，我们把上面的做法搬过来即可。

如果要经过非树边，考虑枚举其经过的某个端点 p，则我们可以更新 dis(i, p) + dis(p, j) \leq f_i 的 j。对每条非树边选一个端点像分治中心那样处理即可。

时间复杂度为 O(n((m - n) + \log n))。

代码：

#include <queue>
#include <cstdio>

using namespace std;

typedef long long ll;

typedef struct {
    int nxt;
    int end;
} Edge;

typedef struct Node_tag {
    ll dis;
    int pos;
    Node_tag(ll dis_, int pos_){
        dis = dis_;
        pos = pos_;
    }
} Node;

int cnt = 1;
int f[200007], c[200007], w[200007], head[200007], extra[47], epos[47][200007], edis[47][200007], fa[200007], depth[200007], size[200007], max_size[200007], pre[27], l[200007], tdis[27][200007], tpos[27][200007], r[200007], tcur[200007], ecur[47];
ll dis[200007], ans[200007];
bool vis1[200007], mark[400087], vis2[200007], vis3[27][200007], vis4[200007];
Edge edge[400087];
queue<int> q;
priority_queue<Node> pq;

bool operator <(const Node a, const Node b){
    return a.dis > b.dis;
}

inline void init(int n, int m){
    for (register int i = 1; i <= n; i++){
        tcur[i] = l[i];
        dis[i] = 0x7fffffffffffffffll;
        vis4[i] = false;
    }
    for (register int i = 1; i <= m; i++){
        ecur[i] = 1;
    }
}

inline void add_edge(int start, int end){
    cnt++;
    edge[cnt].nxt = head[start];
    head[start] = cnt;
    edge[cnt].end = end;
}

void dfs1(int u, int father, int &cnt){
    vis1[u] = true;
    for (register int i = head[u]; i != 0; i = edge[i].nxt){
        int x = edge[i].end;
        if (!vis1[x]){
            dfs1(x, u, cnt);
        } else if (x != father && !mark[i]){
            extra[++cnt] = u;
            mark[i] = mark[i ^ 1] = true;
        }
    }
}

void get_size(int u, int father){
    size[u] = 1;
    for (register int i = head[u]; i != 0; i = edge[i].nxt){
        if (!mark[i]){
            int x = edge[i].end;
            if (x != father && !vis2[x]){
                get_size(x, u);
                size[u] += size[x];
            }
        }
    }
}

void get_centroid(int u, int father, int all, int &ans){
    max_size[u] = all - size[u];
    for (register int i = head[u]; i != 0; i = edge[i].nxt){
        if (!mark[i]){
            int x = edge[i].end;
            if (x != father && !vis2[x]){
                max_size[u] = max(max_size[u], size[x]);
                get_centroid(x, u, all, ans);
            }
        }
    }
    if (ans == -1 || max_size[ans] > max_size[u]) ans = u;
}

inline void solve1(int u){
    l[u] = pre[depth[u]] + 1;
    tdis[depth[u]][u] = 0;
    q.push(u);
    while (!q.empty()){
        int cur = q.front(), dis_i = tdis[depth[u]][cur] + 1;
        q.pop();
        tpos[depth[u]][++pre[depth[u]]] = cur;
        for (register int i = head[cur]; i != 0; i = edge[i].nxt){
            if (!mark[i]){
                int x = edge[i].end;
                if (!vis2[x] && !vis3[depth[u]][x]){
                    vis3[depth[u]][x] = true;
                    tdis[depth[u]][x] = dis_i;
                    q.push(x);
                }
            }
        }
    }
    r[u] = pre[depth[u]];
}

void dfs2(int u, int father){
    int v = -1;
    get_size(u, 0);
    get_centroid(u, 0, size[u], v);
    vis2[v] = true;
    fa[v] = father;
    depth[v] = depth[father] + 1;
    solve1(v);
    for (register int i = head[v]; i != 0; i = edge[i].nxt){
        if (!mark[i]){
            int x = edge[i].end;
            if (!vis2[x]) dfs2(x, v);
        }
    }
}

inline void update(int u, ll k, int n, int cnt){
    for (register int i = u; i != 0; i = fa[i]){
        while (tcur[i] <= r[i] && tdis[depth[i]][u] + tdis[depth[i]][tpos[depth[i]][tcur[i]]] <= f[u]){
            if (!vis4[tpos[depth[i]][tcur[i]]]){
                vis4[tpos[depth[i]][tcur[i]]] = true;
                dis[tpos[depth[i]][tcur[i]]] = k;
                pq.push(Node(k + c[tpos[depth[i]][tcur[i]]], tpos[depth[i]][tcur[i]]));
            }
            tcur[i]++;
        }
    }
    for (register int i = 1; i <= cnt; i++){
        while (ecur[i] <= n && edis[i][u] + edis[i][epos[i][ecur[i]]] <= f[u]){
            if (!vis4[epos[i][ecur[i]]]){
                vis4[epos[i][ecur[i]]] = true;
                dis[epos[i][ecur[i]]] = k;
                pq.push(Node(k + c[epos[i][ecur[i]]], epos[i][ecur[i]]));
            }
            ecur[i]++;
        }
    }
}

inline void solve2(int n, int cnt){
    init(n, cnt);
    dis[1] = 0;
    vis4[1] = true;
    pq.push(Node(c[1], 1));
    for (register int i = 1; i <= n; i++){
        Node cur = pq.top();
        pq.pop();
        update(cur.pos, cur.dis, n, cnt);
    }
    for (register int i = 1; i <= n; i++){
        ans[i] = min(ans[i], dis[i]);
    }
}

int main(){
    int n, m, tmax, cnt = 0;
    scanf("%d %d %d", &n, &m, &tmax);
    for (register int i = 1; i <= n; i++){
        scanf("%d %d %d", &f[i], &c[i], &w[i]);
    }
    for (register int i = 1; i <= m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        add_edge(x, y);
        add_edge(y, x);
    }
    dfs1(1, 0, cnt);
    for (register int i = 1; i <= cnt; i++){
        for (register int j = 1; j <= n; j++){
            edis[i][j] = 0x7fffffff;
        }
        edis[i][extra[i]] = 0;
        q.push(extra[i]);
        for (register int j = 1; j <= n; j++){
            int cur = q.front(), dis_i = edis[i][cur] + 1;
            q.pop();
            epos[i][j] = cur;
            for (register int k = head[cur]; k != 0; k = edge[k].nxt){
                int x = edge[k].end;
                if (edis[i][x] == 0x7fffffff){
                    edis[i][x] = dis_i;
                    q.push(x);
                }
            }
        }
    }
    dfs2(1, 0);
    for (register int i = 1; i <= n; i++){
        ans[i] = 0x7fffffffffffffffll;
    }
    solve2(n, cnt);
    tmax--;
    for (register int i = 1; i <= n; i++){
        c[i] += w[i] * tmax;
    }
    solve2(n, cnt);
    for (register int i = 1; i <= n; i++){
        printf("%lld\n", ans[i]);
    }
    return 0;
}