Luogu P2446 [SDOI2010]大陆争霸

题目描述

https://www.luogu.com.cn/problem/P2446

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，有一些点被其它点所保护，对于点 $i$，其保护点为 $l_i$，只有你到达过 $l_i$ 之后才能到 $i$，保证 $l_1=0$，求点 $1$ 到点 $n$ 的最短路

Solution

注意到我们每次只能拿已经破坏掉结界的点去松弛其他点

所以这东西本质上还是一个 $dijkstra$，只不过只有当一个点的结界被破坏掉才能入队

我们令 $d1[u]$ 表示到达点 $u$ 时间，$d2[u]$ 表示点 $u$ 的结界被破坏掉的时间

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#define maxn 3010
#define maxm 70010
#define ll long long
#define INF 100000000000000000ll
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++;
}

vector<int> A[maxn];
int in[maxn];

struct Queue {
    int k; ll d;

    friend bool operator < (const Queue &u, const Queue &v) { return u.d > v.d; }
}; bool vis[maxn]; ll d1[maxn], d2[maxn];
priority_queue<Queue> Q;
void dijkstra(int s) {
    fill(d1, d1 + maxn, INF); d1[s] = 0;
    Q.push({ s, 0 });
    while (!Q.empty()) {
        int u = Q.top().k; Q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (auto v : A[u]) {
            d2[v] = max({ d2[v], d1[u], d2[u] });
            if (--in[v] == 0) Q.push({ v, max(d1[v], d2[v]) }); 
        }
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (d1[v] > max(d1[u], d2[u]) + w) {
                d1[v] = max(d1[u], d2[u]) + w; 
                if (!in[v]) Q.push({ v, max(d1[v], d2[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); 
    }
    for (int i = 1; i <= n; ++i) {
        int l; cin >> l; in[i] = l; 
        for (int j = 1; j <= l; ++j) {
            int x; cin >> x;
            A[x].push_back(i); 
        }
    } dijkstra(1); cout << max(d1[n], d2[n]) << "\n"; 
    return 0;
}