本文最后更新于：2023年1月30日 晚上
Background
$\text{For in the end, I shall become the last one, who stand victories!}$
翻译一下（与原文极度不符，这边建议看原文）：我记得我被这题恶心了 5 遍了，每一遍听都没透彻，第五遍An过后决心弄透彻掉，然后就明白了，然后就写篇题解纪念一下对这道题最终的胜利。
Analysis
题目中有些城市是被保护着的，必须先解决掉所有保护它的城市才能解决掉它。
初看并不好做，实际上我们可以考虑用到达它的时间和炸掉它的时间，这两者取 $\max$ 即为到达这座城市的实际时间。
设到达第 $i$ 号城市的时间为 $\operatorname{arr_i}$，能进入（也即是将全部的防御炸光的时间）为 $\operatorname{ent_i}$。
如果实际进程的时间为 $\operatorname{dis_i}$，那么根据定义可知：
$\operatorname{dis_i} = \max(arr_i，ent_i)$
考虑到达一个点的实际情况是这样的：
我们到了，但是防御没有全部攻破，这时候我们只能等待。
我们还没到，但是防御早拆完了，这时候我们得等它赶过去。
这就是上式的原因。
那么，$\operatorname{arr}$ 如何求呢？
我们发现，到达一个点的时间就是实际进入起点的时间加上边权，这样我们求出了 $\operatorname{arr}$。
$\operatorname{arr_v} = \min(\operatorname{arr_v}, \operatorname{dis_u + w})$
其实这就是个最短路的事，但我们要让其尽可能得小。
$\operatorname{ent}$ 呢？
考虑到击破全部防御的时间无非就是实际进入所有能防御这个城市的城市的时间，在这些实际时间里取 $\max$ 即可。
注意，$\operatorname{ent}$ 数组不要初始化成正无穷！因为你要取 $\max$！
$\operatorname{ent_v} = \max(\operatorname{ent_v}, \operatorname{dis_u})$
具体如何实现呢？
我们直接在 $\text{Dijkstra}$ 的时候，更新 $\operatorname{arr}$，并更新 $\operatorname{ent}$，两者顺序无所谓，只要你在更新两者的同时不要忘记更新 $\operatorname{dis}$ 即可。
最后，一定要读清题！
Code
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 <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
ll rd() {
ll x = 0, w = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') w = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
return x * w;
}
const int N = 3e3 + 5, M = 7e4 + 5;
int n, m;
struct Graph {
int v, nxt;
ll w;
}e[M << 1], pro[M << 2];
int lk[N], ltp;
int lkp[N], ltpp;
int in[N];
bool vis[N];
ll dis[N];
ll arr[N], ent[N];
void ins(int u, int v, ll w) {
e[++ltp] = (Graph) {v, lk[u], w};
lk[u] = ltp;
}
void ins_pro(int u, int v) {
pro[++ltpp].v = v, pro[ltpp].nxt = lkp[u];
lkp[u] = ltpp;
}
struct HeapNode {
#define HN HeapNode
int pos;
ll dis;
bool operator < (const HN &x) const {
return x.dis < dis;
}
HN (int pos, ll dis) : pos(pos), dis(dis) {}
};
void dijkstra(int s) {
memset(arr, 0x3f, sizeof(arr));
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
arr[s] = 0;
ent[s] = 0;
priority_queue <HN> q;
q.push(HN(s, 0));
while(!q.empty()) {
int u = q.top().pos;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = lkp[u]; i; i = pro[i].nxt) {
int v = pro[i].v;
ent[v] = max(ent[v], dis[u]);
--in[v];
if(!in[v]) {
dis[v] = max(ent[v], arr[v]);
q.push(HN(v, dis[v]));
}
}
for(int i = lk[u]; i; i = e[i].nxt) {
int v = e[i].v;
ll w = e[i].w;
if(arr[v] > dis[u] + w) {
arr[v] = dis[u] + w;
if(!in[v]) {
dis[v] = max(ent[v], arr[v]);
q.push(HN(v, dis[v]));
}
}
}
}
}
int main() {
n = rd(), m = rd();
for(int i = 1; i <= m; ++i) {
int u = rd(), v = rd();
ll w = rd();
ins(u, v, w);
}
for(int u = 1; u <= n; ++u) {
int k = rd();
if(k == 0) continue;
in[u] = k;
for(int j = 1; j <= k; ++j) {
int v = rd();
ins_pro(v, u);
}
}
dijkstra(1);
printf("%lld", dis[n]);
return 0;
}
|