CF 1486E Paired Payment

题目描述

https://codeforces.com/contest/1486/problem/E

简要题意：给定一个 $n$ 个点 $m$ 条边的带权无向图，你每次必须连续走两条边，新的边权为 $(w_1+w_2)^2$，求 $1$ 到其它所有点的最短路

$n\le 10^5,m\le 2\times 10^5,w_i\le 50$

Solution

注意到边权很小，我们考虑对于每个边权都拆点

我们对于一个点拆成 $51$ 个，其中一个代表原始点，另外 $50$ 个代表到这个点且边权为 $w$

对于原图一条边 $(u,v,w)$，我们首先将 $u$ 连 $(v,w)$，边权为 $0$

然后将 $(u,i)$ 连 $v$，边权为 $(i+w)^2$，其中 $i\in [1,50]$

然后我们跑 $dijkstra$ 即可，时间复杂度 $O(50m\log (50m))$

#include <iostream>
#include <cstdio>
#include <queue>
#define maxn 100010
#define maxm 200010
#define Maxn 52 * maxn
#define Maxm 110 * maxm
#define INF 1000000000
#define ll long long
using namespace std;

int n, m; 

struct Edge {
    int to, next, w;
} e[Maxm]; int c1, head[Maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

inline void Add_edge(int u, int v, int w) {
    for (int i = 1; i <= 50; ++i)
        add_edge(u + i * n, v, (i + w) * (i + w));
    add_edge(u, v + w * n, 0); 
}

struct Queue {
    int k, d;

    friend bool operator < (const Queue &u, const Queue &v) { return u.d > v.d; } 
}; bool vis[Maxn]; int dis[Maxn];
priority_queue<Queue> Q; 
void dijkstra(int s) {
    fill(dis, dis + Maxn, INF); dis[s] = 0;
    Q.push({ s, 0 });
    while (!Q.empty()) {
        int u = Q.top().k; Q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push({ v, dis[v] }); 
            }
        }
    }       
} 

int main() { fill(head, head + Maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        Add_edge(x, y, z); Add_edge(y, x, z); 
    } dijkstra(1);
    for (int i = 1; i <= n; ++i)
        cout << (dis[i] == INF ? -1 : dis[i]) << " \n"[i == n]; 
    return 0;
}