DDOSvoid's Blog

CF 1473E Minimum Path

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目描述

https://www.codeforces.com/problemset/problem/1473/E

简要题意：给定一张 $n$ 个点 $m$ 条边的带权无向图，对于一条路径 $E$，这条路径的权值是 $\sum_{i\in E} w_i-max_{i\in E}w_i+min_{i\in E}w_i$，求 $1$ 到其它所有点的最短路

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

Solution

我们考虑弱化条件，即我们不一定要减去最大值加上最小值，我们随便删一条边加以一条边，注意到这样相当于将图分层求最短路

时间复杂度 $O(n\log m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
	#include <iostream>
#include <queue>
#define maxn 200010
#define maxm 200010
#define INF 1000000000000000000
#define ll long long
using namespace std;

int n, m;

struct Edge {
    int to, next, w;
} e[maxm * 2]; 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++;
}

struct node {
    ll v; int k, p1, p2; 

    friend bool operator < (const node &u, const node &v) { return u.v > v.v; } 
};

bool vis[maxn][2][2]; ll dis[maxn][2][2]; int s = 1; 
void dijkstra() {
    fill(vis[0][0], vis[0][0] + maxn * 2 * 2, 0); 
    fill(dis[0][0], dis[0][0] + maxn * 2 * 2, INF); dis[s][0][0] = 0; 
    priority_queue<node> Q; Q.push({ dis[s][0][0], s, 0, 0 });
    while (!Q.empty()) {
        node t = Q.top(); Q.pop();
        int u = t.k, p1 = t.p1, p2 = t.p2;
        if (vis[u][p1][p2]) continue; vis[u][p1][p2] = 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            for (int q1 = p1; q1 < 2; ++q1)
                for (int q2 = p2; q2 < 2; ++q2) {
                    ll d = dis[u][p1][p2] + w + (q1 > p1) * (-w) + (q2 > p2) * w;
                    if (dis[v][q1][q2] > d) {
                        dis[v][q1][q2] = d;
                        Q.push({ dis[v][q1][q2], v, q1, q2 });
                    }
                }
        }
    }
}

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();
    for (int i = 2; i <= n; ++i) cout << dis[i][1][1] << " \n"[i == n];
    return 0;
}