题解：CF1486E Paired Payment

HermesShine · 2026-08-06 15:54:36 · 题解

思路

注意范围 w \le 50，所以可以在跑迪杰斯特拉进行松弛时的时候维护上一个的边权。

如果 j=0，代表 i 为中点，所以这个点到相邻节点的边权为 0。

否则，代表 i 为中转点，说明这个节点到相邻节点的边权为上一个边权与这个边权的和的平方。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, W = 51;
struct edge {
    int u, w;
};
struct node {
    int u, c, w;
    bool operator <(const node &h) const {return w > h.w;}
};
int dis[N][W];
bool vis[N][W];
vector <edge> e[N];
int n, m;
void unionn(int x, int y, int w) {e[x].push_back({y, w});}
void dij() {
    for (int i = 1; i <= n; ++i) 
        for (int j = 0; j <= 50; ++j) dis[i][j] = 1e18;
    priority_queue <node> pq;
    pq.push({1, 0, 0});
    dis[1][0] = 0;
    while (!pq.empty()) {
        node Q = pq.top();
        pq.pop();
        if (vis[Q.u][Q.c]) continue;
        vis[Q.u][Q.c] = 1;
        for (auto [v, w] : e[Q.u]) {
            if (Q.c == 0) {
                if (dis[v][w] > dis[Q.u][0]) {
                    dis[v][w] = dis[Q.u][0];
                    pq.push({v, w, dis[v][w]}); // v下一次转移为中转点
                }
            }
            else {
                if (dis[v][0] > dis[Q.u][Q.c] + (Q.c + w) * (Q.c + w)) {
                    dis[v][0] = dis[Q.u][Q.c] + (Q.c + w) * (Q.c + w);
                    pq.push({v, 0, dis[v][0]}); // 那么下一次转移时，v变为中点
                }
            }
        }
    }
    return ;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; ++i) {
        cin >> u >> v >> w;
        unionn(u, v, w), unionn(v, u, w);
    }
    dij();
    for (int i = 1; i <= n; ++i) 
        cout << (dis[i][0] == 1e18 ? -1 : dis[i][0]) << ' ';
    return 0;
}