2022杭电多校1 H Path

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7145

简要题意：给定一个 $n$ 个点 $m$ 条边的无向带权图，图中有两种边，一种是普通边，一种是特殊边，在经过一次特殊边后到达点 $u$，对于与 $u$ 直接相连的点 $v$，其边权从 $w$ 变为 $w-k$，$k$ 是一开始就给定的一个常数，而与 $u$ 不直接相连的点 $v$，可以花费 $0$ 直接到达，求点 $1$ 到其它所有点的最短路

$n,m\le 10^6,w,k\le 10^9$

Solution

首先拆点，将 $u$ 拆成 $(u,0)$ 和 $(u,1)$，表示是否经过了特殊边到达 $u$

考虑 $dijkstra$ 的过程，每当经过一次特殊边后，我们会拿 $dis_{u,1}$ 去更新所有与 $u$ 不直接相连的点 $v$ 的 $dis_{v,0}$，注意到 $dis_{u,1}$ 在 $dijkstra$ 的过程是递增的，也就说通过这种特殊边的更新，每个 $dis_{v,0}$ 只会有一次

所以我们拿一个 $vector$ 存储所有还没有被特殊边更新过的 $v$，然后对于每个 $u$，我们直接暴力 $vector$ 去更新所有与其不直接相连的 $v$，并将其删除

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

#include <iostream>
#include <algorithm>
#include <queue>
#define maxn 1000010
#define ll long long
#define INF 1000000000000000000
using namespace std;

int n, m, k; 

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

struct node {
    int k, t; ll d;

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

bool vis[maxn][2], use[maxn]; ll dis[maxn][2]; int s; 
void dijkstra() {
    priority_queue<node> Q; Q.push({ s, 0 });
    for (int i = 1; i <= n; ++i) dis[i][0] = dis[i][1] = INF; dis[s][0] = 0;
    for (int i = 1; i <= n; ++i) vis[i][0] = vis[i][1] = 0;
    vector<int> vec; for (int i = 1; i <= n; ++i) vec.push_back(i);
    while (!Q.empty()) {
        int u = Q.top().k, o = Q.top().t; Q.pop();
        if (vis[u][o]) continue; vis[u][o] = 1;
        for (int i = head[u]; ~i; i = e[i].next) use[e[i].to] = 1;
        if (o) {
            vector<int> tmp;
            for (auto v : vec) { 
                if (use[v]) { tmp.push_back(v); continue; }
                if (dis[v][0] > dis[u][o]) {
                    dis[v][0] = dis[u][o];
                    Q.push({ v, 0, dis[v][0] });
                }
            } vec = tmp;
        }
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w - o * k, p = e[i].fi;
            if (dis[v][p] > dis[u][o] + w) {
                dis[v][p] = dis[u][o] + w;
                Q.push({ v, p, dis[v][p] });
            }
        }
        for (int i = head[u]; ~i; i = e[i].next) use[e[i].to] = 0;
    }
}

void work() {
    cin >> n >> m >> s >> k;
    for (int i = 1; i <= n; ++i) head[i] = -1; c1 = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y, z, w; cin >> x >> y >> z >> w;
        add_edge(x, y, z, w); 
    } dijkstra();
    for (int i = 1; i <= n; ++i) {
        ll v = min(dis[i][0], dis[i][1]);
        cout << (v == INF ? -1 : v) << " ";
    } cout << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T; 
    while (T--) work(); 
    return 0;
}