[SDOI2010] 大陆争霸

GitHub 跳转原题关系图返回列表

对每个城市分别维护“机器人最早能到城门的时间”和“所有前置发生器最晚被摧毁的时间”，城市真正被摧毁的时间是这两者的最大值，再用 Dijkstra 式过程按时间推进。

OJ: luogu

题目 ID: P2446

难度:提高+/省选-

标签:最短路图论思维堆

日期: 2026-06-20 05:10

题意

有 N 个城市和 M 条单向道路，从城市 1 出发，要摧毁城市 N。

但进入某个城市之前，必须先摧毁维持它结界的所有发生器。
这些发生器分布在其他城市中。

机器人是无限的。
一旦机器人进入某个城市，就可以立刻自爆并摧毁这个城市里的一个目标，因此这个城市里的发生器也会在那一刻被摧毁。

问最短多久能摧毁城市 N。

思路

先看一个更直观的小数据暴力：

cpp

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const long long INF = (1LL << 60);

int n, m;
vector<pair<int, int> > roads[MAXN];
vector<int> depend[MAXN];
long long answer[MAXN];
long long road_arrive[MAXN];
long long shield_need[MAXN];
int remain_need[MAXN];
bool vis[MAXN];

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        roads[i].clear();
        depend[i].clear();
    }

    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        roads[u].push_back(make_pair(v, len));
    }

    for (int city = 1; city <= n; city++) {
        int k;
        cin >> k;
        remain_need[city] = k;
        for (int j = 1; j <= k; j++) {
            int generator_city;
            cin >> generator_city;
            depend[generator_city].push_back(city);
        }
    }

    for (int i = 1; i <= n; i++) {
        answer[i] = INF;
        road_arrive[i] = INF;
        shield_need[i] = 0;
        vis[i] = false;
    }

    answer[1] = 0;

    // 更直接的小数据写法：
    // 每次暴力找“当前最早可以被摧毁的那个城市”。
    for (int step = 1; step <= n; step++) {
        int choose = 0;
        for (int city = 1; city <= n; city++) {
            if (vis[city]) {
                continue;
            }
            if (city == 1) {
                choose = 1;
                break;
            }
            if (remain_need[city] != 0) {
                continue;
            }
            if (road_arrive[city] >= INF / 2) {
                continue;
            }
            long long cand = max(road_arrive[city], shield_need[city]);
            if (cand < answer[city]) {
                answer[city] = cand;
            }
            if (choose == 0 || answer[city] < answer[choose]) {
                choose = city;
            }
        }

        vis[choose] = true;

        for (size_t i = 0; i < roads[choose].size(); i++) {
            int v = roads[choose][i].first;
            long long nd = answer[choose] + roads[choose][i].second;
            if (nd < road_arrive[v]) {
                road_arrive[v] = nd;
            }
        }

        for (size_t i = 0; i < depend[choose].size(); i++) {
            int v = depend[choose][i];
            remain_need[v]--;
            if (answer[choose] > shield_need[v]) {
                shield_need[v] = answer[choose];
            }
        }
    }

    cout << answer[n] << '\n';

    return 0;
}

brute.cpp 的想法很直接：

每次暴力枚举当前“最早可能被摧毁”的那个城市
摧毁它之后：
- 它会沿着道路给别的城市带来更早的到达时间
- 它作为发生器，也会解开一批城市的结界限制
重复这个过程直到首都被摧毁

这个过程最贴题意，但大数据下用暴力找下一个城市太慢。

两个时间都要维护

对一个城市 v 来说，想真正摧毁它，必须同时满足两件事：

至少有一个机器人已经能到达它的城门
它的所有前置发生器都已经被摧毁

所以我们分别维护两个量：

road_arrive[v]：最早什么时候能有机器人到达 v
shield_need[v]：为了进入 v，它所有前置发生器最晚被摧毁的时间

那么城市 v 真正能被摧毁的最早时间就是：

max(road_arrive[v], shield_need[v])

这张图展示的就是这个关系：

flowchart LR
  A["road_arrive[v]"] --> C["capture[v] = max(A, B)"]
  B["shield_need[v]"] --> C

图里真正要看的，是“路走到了”还不够，结界也必须同时解开。
而如果结界先解开，机器人也可以之后再到；
如果机器人先到，理论上也可以在城外等到结界全部失效。

为什么可以像 Dijkstra 一样做

当一个城市 u 在时间 answer[u] 被摧毁之后，它只会带来两类影响：

沿道路更新别的城市的 road_arrive
作为发生器，更新它所控制城市的 shield_need

这两类信息都会让别的城市“更早可达”，不会让答案变差。
因此我们可以像 Dijkstra 那样，每次取当前最早能被摧毁的城市继续扩展。

具体做法：

城市 1 初始就在我方手中，时间记为 0
用优先队列维护当前候选的最早摧毁时间
每摧毁一个城市，就更新：
- 它沿道路能到达的城市
- 依赖它作为发生器的城市
如果某个城市已经满足：
- 所有前置发生器都处理完
- 并且已有机器人能到它门口
就可以用 max(road_arrive, shield_need) 去尝试更新答案

代码

cpp

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3000 + 5;
const int MAXM = 70000 + 5;
const long long INF = (1LL << 60);

struct HeapNode {
    int u;
    long long dist;

    bool operator < (const HeapNode &other) const {
        return dist > other.dist;
    }
};

int n, m;
int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM], edge_cnt;

long long answer[MAXN];      // 城市最早被摧毁的时间
long long road_arrive[MAXN]; // 已经摧毁的城市中，最早什么时候能派机器人到这个城市门口
long long shield_need[MAXN]; // 所有前置结界发生器被摧毁后的最晚时间
int remain_need[MAXN];       // 还有多少前置发生器没被摧毁
bool vis[MAXN];

vector<int> depend[MAXN];    // 城市 u 的发生器会影响哪些城市

void init_graph() {
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
        depend[i].clear();
    }
}

void add_edge(int u, int v, int len) {
    edge_cnt++;
    to[edge_cnt] = v;
    w[edge_cnt] = len;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void try_update_city(int v, priority_queue<HeapNode> &pq) {
    if (vis[v]) {
        return;
    }
    if (remain_need[v] != 0) {
        return;
    }
    if (road_arrive[v] >= INF / 2) {
        return;
    }

    long long cand = max(road_arrive[v], shield_need[v]);
    if (cand < answer[v]) {
        answer[v] = cand;
        pq.push({v, cand});
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        answer[i] = INF;
        road_arrive[i] = INF;
        shield_need[i] = 0;
        vis[i] = false;
    }

    priority_queue<HeapNode> pq;

    // 城市 1 已经被我方控制，时间记为 0。
    answer[1] = 0;
    pq.push({1, 0});

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.u;
        if (vis[u]) {
            continue;
        }
        vis[u] = true;

        // 从已经摧毁的城市 u 出发，派机器人沿单向道路去其他城市门口。
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            long long nd = answer[u] + w[i];
            if (nd < road_arrive[v]) {
                road_arrive[v] = nd;
                try_update_city(v, pq);
            }
        }

        // u 城市里的发生器已经被摧毁，它会解开一批城市的结界限制。
        for (size_t i = 0; i < depend[u].size(); i++) {
            int v = depend[u][i];
            remain_need[v]--;
            if (answer[u] > shield_need[v]) {
                shield_need[v] = answer[u];
            }
            try_update_city(v, pq);
        }
    }
}

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

    cin >> n >> m;
    init_graph();

    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        add_edge(u, v, len);
    }

    for (int city = 1; city <= n; city++) {
        int k;
        cin >> k;
        remain_need[city] = k;
        for (int j = 1; j <= k; j++) {
            int generator_city;
            cin >> generator_city;
            depend[generator_city].push_back(city);
        }
    }

    solve();
    cout << answer[n] << '\n';

    return 0;
}

复杂度

设发生器依赖关系总数为 R。

每条道路最多参与常数次松弛，每条依赖关系也只会处理一次。
优先队列复杂度为：

$O((M+R) \log N)$

空间复杂度：

$O(M + R + N)$

总结

这题表面上像最短路，实际上多了一层“结界前置条件”。

最关键的想法就是把一个城市的最早摧毁时间拆成两部分：

机器人最早什么时候能到
前置发生器最晚什么时候才会全部被摧毁

最后取两者最大值。
一旦这个式子想清楚，整题就能顺着 Dijkstra 的推进方式写出来。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P2446 [SDOI2010] 大陆争霸

题目背景

在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。

幻想历 $8012$ 年 $1$ 月，杰森国正式宣布曾·布拉泽是他们唯一信仰的神，同时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。

幻想历 $8012$ 年 $3$ 月 $2$ 日，位于杰森国东部小镇神谕镇的克里斯国教徒发动起义。

幻想历 $8012$ 年 $3$ 月 $7$ 日，神谕镇的起义被杰森国大军以残酷手段镇压。

幻想历 $8012$ 年 $3$ 月 $8$ 日，克里斯国对杰森国宣战。由数十万大军组成的克里斯军团开至两国边境，与杰森军团对峙。

幻想历 $8012$ 年 $4$ 月，克里斯军团攻破杰森军团防线进入神谕镇，该镇幸存的克里斯国教徒得到解放。

战争随后进入胶着状态，旷日持久。战况惨烈，一时间枪林弹雨，硝烟弥漫，民不聊生。

题目描述

幻想历 $8012$ 年 $5$ 月 $12$ 日深夜，斯普林·布拉泽降下神谕：“Trust me, earn eternal life.”克里斯军团士气大增。作为克里斯军团的主帅，你决定利用这一机会发动奇袭，一举击败杰森国。具体地说，杰森国有 $N$ 个城市，由 $M$ 条单向道路连接。神谕镇是城市 $1$ 而杰森国的首都是城市 $N$ 。你只需摧毁位于杰森国首都的曾·布拉泽大神殿，杰森国的信仰，军队还有一切就都会土崩瓦解，灰飞烟灭。

为了尽量减小己方的消耗，你决定使用自爆机器人完成这一任务。唯一的困难是，杰森国的一部分城市有结界保护，不破坏掉结界就无法进入城市。而每个城市的结界都是由分布在其他城市中的一些结界发生器维持的，如果想进入某个城市，你就必须破坏掉维持这个城市结界的所有结界发生器。

现在你有无限多的自爆机器人，一旦进入了某个城市，自爆机器人可以瞬间引爆，破坏一个目标（结界发生器，或是杰森国大神殿），当然机器人本身也会一起被破坏。你需要知道：摧毁杰森国所需的最短时间。

输入格式

第一行两个正整数 $N,M$ 。

接下来 $M$ 行，每行三个正整数 $u_i,v_i,w_i$ ，表示有一条从城市 $u_i$ 到城市 $v_i$ 的单向道路，自爆机器人通过这条道路需要 $w_i$ 的时间。

之后 $N$ 行，每行描述一个城市。首先是一个正整数 $l_i$ ，维持这个城市结界所使用的结界发生器数目。之后 $l_i$ 个 $1\ldots N$ 之间的城市编号，表示每个结界发生器的位置。如果 $l_i=0$ ，则说明该城市没有结界保护，保证 $l_1 = 0$ 。

输出格式

仅包含一个正整数，击败杰森国所需的最短时间。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

对于 $20\%$ 的数据，满足 $N\leq 15$ ， $M≤50$ ；

对于 $50\%$ 的数据，满足 $N\leq 500$ ， $M\leq 6\times 10^3$ ；

对于 $100\%$ 的数据，满足 $1\leq N\leq 3\times 10^3$ ， $1\leq M\leq 7\times 10^4$ ， $1\leq w_i\leq 10^8$ 。

输入数据保证一定有解，且不会存在维持某个城市结界的结界发生器在这个城市内部。

连接两个城市的道路可能不止一条，也可能存在一个城市自己到自己的道路。

[SDOI2010] 大陆争霸

目录

题意

思路

两个时间都要维护

为什么可以像 Dijkstra 一样做

代码

复杂度

总结

一图流解析