多校省选模拟4

目前只会 A

A

题意

给你一个 \(n\) 个点 \(m\) 个图，然后你要从 \(S\) 走到 \(T\)，然后，你可以使用一次能力，从 \(x\) 走到 \(y\)，花费 \((x-y)^2\)。

题解

我们这题很简单，怎么做呢，我们考虑，算出来 \(S\) 到每个点的路径长度，然后算出来 \(T\) 到每个点的路径长度。

然后，我们的答案相当于是

\[\min(dis1[x]+x^2+dis2[y]+y^2-2xy) \]

那么，我们可以，用类似于斜率优化的东西，我们把 \(dis1[x] + x ^ 2\) 记为 \(c(x)\)。

然后，我们的答案就是

\[\min_{1\le x \le N} {(c(x)+\min_{1\le y \le n}(dis2[y] + y ^ 2 - 2xy))} \]

那么相当于是，我们每个决策点的坐标是 \((y,dis2[y]+y^2)\)，然后每次的斜率递增为 \(2x\)，先把下凸壳做出来，然后直接在上面扫就完了。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::pair;
using std::priority_queue;
using std::vector;
template <typename T>
inline T min(const T &x, const T &y) {
    return x < y ? x : y;
}
template <typename T>
inline T max(const T &x, const T &y) {
    return x > y ? x : y;
}
const int MAXN = 2e5 + 10, MAXM = 4e5 + 10;
const double eps = 1e-8;
int N, M, S, T, U[MAXM], V[MAXM], W[MAXM], hd, tl, Q[MAXN];
long long dis[MAXN], F[MAXN], G[MAXN], ANS[MAXN];
bool vis[MAXN];
vector<pair<int, int>> e[MAXN];
void getdis(int x) {
    for (int i = 1; i <= N; ++i) {
        e[i].clear();
    }
    if (x == S) {
        for (int i = 1; i <= M; ++i) {
            e[U[i]].emplace_back(V[i], W[i]);
        }
    } else {
        for (int i = 1; i <= M; ++i) {
            e[V[i]].emplace_back(U[i], W[i]);
        }
    }
    memset(vis, 0, sizeof vis);
    memset(dis, 63, sizeof dis);
    dis[x] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, std::greater<pair<long long, int>>> Q;
    Q.emplace(0, x);
    while (Q.size()) {
        int u = Q.top().second;
        Q.pop();
        if (vis[u]) {
            continue;
        }
        vis[u] = 1;
        for (auto &i : e[u]) {
            if (dis[i.first] > dis[u] + i.second) {
                Q.emplace(dis[i.first] = dis[u] + i.second, i.first);
            }
        }
    }
    return;
}
int main() {
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> S >> T;
    for (int i = 1; i <= M; ++i) {
        cin >> U[i] >> V[i] >> W[i];
    }
    getdis(S);
    for (int i = 1; i <= N; ++i) {
        F[i] = dis[i] + (long long)i * i;
    }
    getdis(T);
    for (int i = 1; i <= N; ++i) {
        G[i] = dis[i] + (long long)i * i;
    }
    hd = 1;
    tl = 0;
    for (int i = 1; i <= N; ++i) {
        while (hd < tl && (G[i] - G[Q[tl]]) * 1.0 / (i - Q[tl]) <=
                              (G[Q[tl]] - G[Q[tl - 1]]) * 1.0 / (Q[tl] - Q[tl - 1]) + eps) {
            tl--;
        }
        Q[++tl] = i;
    }
    for (int i = 1; i <= N; ++i) {
        while (hd < tl && (G[Q[hd + 1]] - G[Q[hd]]) * 1.0 / (Q[hd + 1] - Q[hd]) <= i * 2 + eps) {
            ++hd;
        }
        ANS[i] = F[i] + G[Q[hd]] - (long long)2 * i * Q[hd];
    }
    long long ret = F[T] - (long long)T * T;
    for (int i = 1; i <= N; ++i) {
        ret = min(ret, ANS[i]);
    }
    cout << ret << '\n';
    return 0;
}