OI笔记 | 2023.4-6 做题记录（二）
[SBCOI2020] 时光的流逝
这个游戏是在一个有向图（不保证无环）上进行的。每轮游戏开始前，她们先在图上选定一个起点和一个终点，并在起点处放上一枚棋子。
然后两人轮流移动棋子，每次可以将棋子按照有向图的方向移动至相邻的点。
如果谁先将棋子移动至终点，那么谁就胜利了。同样，如果谁无法移动了，那么谁就失败了。
两人轮流操作，请问，他们是否有必胜策略呢？
答案为一个整数 0 或 1 或 -1，其中 1 表示（先手）有必胜策略，-1 表示后手有必胜策略，0 表示两人均无必胜策略。
$1\leq n\leq 10^5$，$1\leq m\leq 5\times10^5$，$1\leq q\leq 500$。
题解
图上的博弈论，考虑标记必败点和必胜点。必败点或必胜点指的是：当前操作的人处在这个点，他有先手必败策略或先手必胜策略。
根据这个定义，初始时，终点和出度为 $0$ 的点都是必败点。若当前操作的人处在终点，说明上一个操作的人成功走到了终点，所以当前操作的人必败。如果这个点出度为 $0$，那么当前操作的人无处可走，同样必败。
然后我们想要从这些已确定状态的点扩展出其他点的状态。分类讨论一下：
-
若某一个点的出边所有指向的点均为必胜点，则这个点是必败点。
-
如果当前点确定是必败点，则有边连向它的点都是必胜点。
如果暴力进行扩展，需要 $\mathcal{O}(qn^2)$ 的复杂度来枚举。
考虑优化这个过程。由于我们都是从已确定状态的点开始扩展，我们可以建反图进行 bfs。不断将确定状态的点 push 进队列，然后扩展状态即可。检验情况 1（某个点的出边所有指向的点均为必胜点）是否成立，可以通过枚举到必胜点，都让他所连的点的出度减 $1$，然后判减之后出度是否为 $0$ 即可。
时间复杂度 $\mathcal{O}(qm)$。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 1e5 + 10;
int n, m, q, x, y, u, v, out[MAX_N], out_copy[MAX_N], state[MAX_N];
bool vis[MAX_N];
vector<int> G[MAX_N];
int main() {
n = read(), m = read(), q = read();
for(int i = 1; i <= m; i++) {
u = read(), v = read();
G[v].pb(u);
out_copy[u]++;
}
while(q--) {
x = read(), y = read();
queue<int> q;
for(int i = 1; i <= n; i++) {
out[i] = out_copy[i];
vis[i] = state[i] = 0;
if(!out[i] && i != y) {
q.push(i);
state[i] = -1;
vis[i] = 1;
}
}
q.push(y);
state[y] = -1;
vis[y] = 1;
while(!q.empty() && state[x] == 0) {
u = q.front();
q.pop();
for(int v : G[u]) {
if(vis[v]) continue;
if(state[u] == -1) {
state[v] = 1;
vis[v] = 1;
q.push(v);
}
if(state[u] == 1 && --out[v] == 0) {
state[v] = -1;
vis[v] = 1;
q.push(v);
}
}
}
write(state[x]);
putchar('\n');
}
return 0;
}
[CSP-S2020] 函数调用
给定数列 $a_{1\dots n}$，定义了 $m$ 个函数，函数有三种：
$\colorbox{f0f0f0}{\verb!1 p v!}$ 将 $a_p$ 加上 $v$。
$\colorbox{f0f0f0}{\verb!2 v!}$ 将所有数乘上 $v$。
$\colorbox{f0f0f0}{\verb!3 c g1 g2 … gc!}$ 执行函数 $g_1,g_2,\dots g_c$。保证不会出现循环调用。
给定值域为 $[1,m]$ 的序列 $f_{1\dots Q}$，依次调用函数 $f_1,f_2,\dots f_Q$，输出最后得到的 $a_{1\dots n}$，结果对 $998244353$ 取模。
$1\leq n,m,Q\leq 10^5, \sum c \le 10^6$。
题解
函数的调用关系构成一个 DAG。所以如果我们不考虑加法操作，只要记搜一下，就可以得到最终全局要乘的数 $mul_0$。
但是我们发现加法和乘法操作的调用顺序对结果的影响很大。例如我们先进行 $a_p\gets a_p + v$，在这之后所调用的所有乘法操作的乘积为 $k$，则这次加法操作实际上相当于加了 $v\times k$。
设 $k_u$ 为函数 $u$ 的调用次数，则所有加法操作对答案的贡献就是加上的值 $add_u$ 乘上 $k_u$。那我们可以拓扑排序一下，做 DAG 上的 dp 求出每个点的 $k$ 即可。一个点的 $k$ 由它之后执行的所有乘法标记相乘决定。
具体地，我们利用链式前向星加边时自然产生的逆序，从后往前遍历边 $(u,v)$，把 $k_v$ 加上当前乘法标记的乘积 $\alpha$ 乘上前驱的答案 $k_u$，再把 $v$ 的乘法标记乘到 $\alpha$ 上。
#include <bits/stdc++.h>
#define FG(u) for(int i = fir[u], v = t[i].v; i; i = t[i].nxt, v = t[i].v)
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 1e5 + 10, MOD = 998244353;
int Q, n, m, a[MAX_N], in[MAX_N], out[MAX_N];
bool vis[MAX_N];
struct node {
int type, add, mul, pos, cnt;
node() {}
node(int _type, int _add, int _mul, int _pos, int _cnt) :
type(_type), add(_add), mul(_mul), pos(_pos), cnt(_cnt) {}
} d[MAX_N];
int fir[MAX_N], tot;
struct edge {
int v, nxt;
edge() {}
edge(int _v, int _nxt) :
v(_v), nxt(_nxt) {}
} t[MAX_N * 20];
inline void AddEdge(int u, int v) {
t[++tot] = edge(v, fir[u]);
fir[u] = tot;
}
int find(int u) {
if(vis[u]) return d[u].mul;
int ret = d[u].mul;
FG(u)
ret = 1ll * ret * find(v) % MOD;
vis[u] = 1;
return d[u].mul = ret;
}
void topo() {
queue<int> q;
for(int i = 0; i <= m; i++)
if(in[i] == 0) q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
int now = 1;
FG(u) {
d[v].cnt = (d[v].cnt + 1ll * d[u].cnt * now % MOD) % MOD;
now = 1ll * now * d[v].mul % MOD;
if(--in[v] == 0) q.push(v);
}
}
}
int main() {
n = read();
for(int i = 1; i <= n; i++)
a[i] = read();
m = read();
for(int i = 1, type, p, v; i <= m; i++) {
type = read();
if(type == 1) {
p = read(), v = read();
d[i] = node(type, v, 1, p, 0);
}
else if(type == 2) {
v = read();
d[i] = node(type, 0, v, 0, 0);
}
else {
p = read();
d[i] = node(type, 0, 1, 0, 0);
for(int j = 1; j <= p; j++) {
v = read();
AddEdge(i, v);
in[v]++;
}
}
}
d[0] = node(0, 0, 1, 0, 1);
Q = read();
for(int i = 1, v; i <= Q; i++) {
v = read();
AddEdge(0, v);
in[v]++;
}
find(0);
for(int i = 1; i <= n; i++)
a[i] = 1ll * a[i] * d[0].mul % MOD;
topo();
for(int i = 1; i <= m; i++)
if(d[i].type == 1) a[d[i].pos] = (a[d[i].pos] + 1ll * d[i].add * d[i].cnt % MOD) % MOD;
for(int i = 1; i <= n; i++)
write(a[i]), putchar(' ');
return 0;
}
[APIO2012] 派遣
有一棵 $N$ 个点的树，每个点 $i$ 有一个领导力 $l_i$ 和薪水 $c_i$。给定预算 $M$，若让点 $u$ 当领导，则可在 $u$ 的子树中选择一些薪水之和不超过 $M$ 的点。定义满意度为选择的点数 $\times$ 领导的领导力，求最大的满意度。
$n\leq 10^5$
Solution 1
使用可并堆。我们在每个节点上建一个大根堆维护子树内的薪水，再用数组来维护子树的大小和子树中薪水之和。在 dfs 中合并大根堆与数组即可。
只要贪心地不断把大根堆的堆顶删掉，直到薪水之和小于 $M$，更新答案。
显然被删掉的元素不会影响到父亲的答案，贪心策略正确。
时间复杂度 $\mathcal{O}(n\log n)$。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef __gnu_pbds::priority_queue<ll> pq;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 1e5 + 10;
int n, m;
ll sum[MAX_N], ans;
int c[MAX_N], l[MAX_N], siz[MAX_N];
vector<int> G[MAX_N];
pq dfs(int u) {
pq ret;
ret.push(c[u]);
sum[u] = c[u];
siz[u] = 1;
for(int v : G[u]) {
pq t = dfs(v);
sum[u] += sum[v];
siz[u] += siz[v];
ret.join(t);
}
while(!ret.empty() && sum[u] > m) {
sum[u] -= ret.top();
siz[u]--;
ret.pop();
}
if(!ret.empty()) ans = max(ans, 1ll * siz[u] * l[u]);
return ret;
}
int main() {
n = read(), m = read();
for(int i = 1, fa; i <= n; i++) {
fa = read();
G[fa].pb(i);
c[i] = read();
l[i] = read();
}
dfs(1);
write(ans);
return 0;
}
Solution 2
线段树合并。我们先将薪水数组 $c$ 离散化，然后在每一个节点 $i$ 上建一个权值线段树，下标从小到大即为薪水从小到大，把 $c_i$ 加入这个节点的权值线段树中。权值线段树的每个节点上要维护薪水之和、这个区间内的节点个数。
然后我们在权值线段树上二分，对于一个节点 $i$，它的左儿子的薪水较小，右儿子的薪水较大。如果当前预算大于左儿子的薪水之和，则向右儿子递归，并把预算减去左儿子的薪水之和，答案加上左儿子的节点个数；否则向左儿子递归。
时间复杂度 $\mathcal{O}(n\log n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 1e5 + 10;
int n, m, tot, fa[MAX_N], l[MAX_N], rt[MAX_N];
pii t[MAX_N];
ll ans;
struct node {
int lc, rc, cnt;
ll sum;
node() { lc = rc = sum = cnt = 0; }
} d[MAX_N << 5];
inline void pu(int p) {
d[p].sum = d[d[p].lc].sum + d[d[p].rc].sum;
d[p].cnt = d[d[p].lc].cnt + d[d[p].rc].cnt;
}
inline int merge(int x, int y, int s, int t) {
if(!x || !y) return x | y;
if(s == t) {
d[x].sum += d[y].sum;
d[x].cnt += d[y].cnt;
return x;
}
int mid = s + ((t - s) >> 1);
d[x].lc = merge(d[x].lc, d[y].lc, s, mid);
d[x].rc = merge(d[x].rc, d[y].rc, mid + 1, t);
pu(x);
return x;
}
inline int update(int p, int s, int t, int val, int w) {
if(!p) p = ++tot;
if(s == t) {
d[p].cnt = 1;
d[p].sum = w;
return p;
}
int mid = s + ((t - s) >> 1);
if(val <= mid) d[p].lc = update(d[p].lc, s, mid, val, w);
else d[p].rc = update(d[p].rc, mid + 1, t, val, w);
pu(p);
return p;
}
inline int search(int p, int s, int t, int lft) {
if(!p) return 0;
if(s == t) return d[p].sum <= lft;
int mid = s + ((t - s) >> 1);
if(d[d[p].lc].sum < lft) return d[d[p].lc].cnt + search(d[p].rc, mid + 1, t, lft - d[d[p].lc].sum);
else return search(d[p].lc, s, mid, lft);
}
int main() {
n = read(), m = read();
for(int i = 1, c; i <= n; i++) {
fa[i] = read(), c = read(), l[i] = read();
t[i] = make_pair(c, i);
}
sort(t + 1, t + n + 1);
for(int i = 1, o; i <= n; i++) {
o = t[i].second;
rt[o] = update(rt[o], 1, n, i, t[i].first);
}
for(int i = n; i >= 1; i--) {
ans = max(ans, 1ll * l[i] * search(rt[i], 1, n, m));
if(fa[i]) rt[fa[i]] = merge(rt[fa[i]], rt[i], 1, n);
}
write(ans), putchar('\n');
return 0;
}
栈
维护 $n$ 个初始为空的栈以及 $m$ 个操作，操作分为以下三种：
push x y z：在编号为 $z$ 的栈中加入 $x$ 个数字 $y$。
pop x z：从第 $z$ 个栈中弹出 $x$ 个数，并输出最后一个数。保证操作合法。
put u v：依次把第 $u$ 个栈中的数弹出并加入到第 $v$ 个栈中。
$n,m\le 2\times 10^5$
题解
考虑我们要支持拼接操作，用双向链表来模拟栈。
由于 put 操作包括翻转操作，使用一种双向链表的实现，即直接建图，把双向链表看做一条链，链上的相邻两点之间有双向边。
对于每个栈 $z$，记录其端点在链表上的位置，包括栈底 $fir_z$ 和栈顶 $lst_z$。所以 put 操作可以 $\mathcal{O}(1)$ 完成，只需把 $lst_u$ 与 $lst_v$ 连接上，再把 $lst_v$ 更新成 $fir_u$ 即可。
时间复杂度 $\mathcal{O}(m)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
inline int read_op() {...}
const int MAX_N = 2e5 + 10;
int n, m, tot, fir[MAX_N], lst[MAX_N];
struct node {
int ch[2], cnt, num;
node() {}
node(int _cnt, int _num) :
cnt(_cnt), num(_num) { ch[0] = ch[1] = 0; }
} d[MAX_N];
inline void U(int x, int y) {
d[x].ch[d[x].ch[0] != 0] = y;
d[y].ch[d[y].ch[0] != 0] = x;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; i++) {
int op = read_op(), x, y, z;
if(op == 1) {
x = read(), y = read(), z = read();
d[++tot] = node(x, y);
if(!fir[z]) fir[z] = lst[z] = tot;
else U(lst[z], tot), lst[z] = tot;
}
else if(op == 2) {
x = read(), z = read();
while(x > d[lst[z]].cnt) {
x -= d[lst[z]].cnt;
y = d[lst[z]].ch[d[lst[z]].ch[0] == 0];
d[y].ch[d[y].ch[0] != lst[z]] = 0;
lst[z] = y;
}
d[lst[z]].cnt -= x;
write(d[lst[z]].num), putchar('\n');
}
else {
x = read(), y = read();
if(!lst[x]) continue;
if(!lst[y]) {
fir[y] = lst[x], lst[y] = fir[x];
fir[x] = lst[x] = 0;
continue;
}
U(lst[x], lst[y]);
lst[y] = fir[x];
fir[x] = lst[x] = 0;
}
}
return 0;
}
七曜圣贤
维护一个集合，初始时为 $\left{ 0,1, \cdots , a \right}$ ，支持以下操作：
-
插入 $x$ $\left (x > a \right )$
-
删除 $x$
-
将最早删除的数插入集合
$T$ 组数据，每组数据由给定的 IO 代码生成，答案由给定的 IO 代码编码。
每组数据后有 $m$ 次操作，每次操作后，求集合的 $\text{mex}$，这里定义为集合里最小的没有出现的非负整数。
$T \leq 50, m \leq 10^6$
题解
操作 $3$ 需要维护一个先进先出的删除序列，直接用队列即可。
考虑对于一个集合，若它包含了 $0,1,2\cdots a$，则它的 $\text{mex}$ 为 $a+1$；若它包含了 $0, 1, \cdots o - 1$ 与 $o + 1,o + 2,\cdots $，则它的 $\text{mex}$ 为 $o$。
那么若有删除操作，则 $\text{mex}$ 要么是被删除的数里的最小值，要么是最小的没有插入的数。
最小的没有插入的数可以暴力维护。
删除序列里的最小值我们可以结合操作 $3$，维护一个可以求队列内最小值的队列。只需要再维护一个单调队列即可。
时间复杂度 $\mathcal{O}(Tm)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
namespace IO{
int c; unsigned int seed; char buf[50];
unsigned int randnum(){
seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5;
return seed;
}
inline ll read() {
ll ret = 0, w = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') w = -1; c = getchar();}
while(isdigit(c)) { ret = (ret << 1) + (ret << 3) + (c ^ 48); c = getchar();}
return ret * w;
}
inline void write(ll x) {
if(x < 0) x = -x, putchar('-');
int tp = 0;
do { buf[++tp] = x % 10 + 48; x /= 10; } while(x);
while(tp) putchar(buf[tp--]);
}
inline void init_case(int &m, int &a, int &b, int &d, int p[]) {
m = read(), seed = read(), a = read(), b = read(), c = read(), d = read();
for(int i = 1; i <= m; i++)
if(randnum() % c == 0) p[i] = -1;
else p[i] = randnum() % b;
}
inline void update_ans(unsigned int &ans_sum, unsigned int cur_ans, int no){
const static unsigned int mod = 998244353;
ans_sum ^= 1ll * no * (no + 7) % mod * cur_ans % mod;
}
}
using namespace IO;
struct MinQue {
queue<int> q; deque<int> dq;
void push(int x) {
q.push(x);
while(!dq.empty() && x < dq.back()) dq.pop_back();
dq.push_back(x);
}
void clear() {
while(!q.empty()) q.pop();
while(!dq.empty()) dq.pop_back();
}
bool empty() { return q.empty(); }
int front() { return q.empty() ? -1 : q.front(); }
int min_ele() { return dq.empty() ? -1 : dq.front(); }
void pop() {
if(q.empty()) return;
int x = q.front(); q.pop();
if(!dq.empty() && dq.front() == x) dq.pop_front();
}
} Q;
const int MAX_N = 2e6 + 10;
int T, m, a, b, d, X, Y, p[MAX_N];
unsigned int ans, cur;
bool buy[MAX_N], vis[MAX_N], flag;
void init() {
init_case(m, a, b, d, p);
memset(buy, 0, sizeof(buy));
memset(vis, 0, sizeof(vis));
Q.clear();
for(int i = 0; i <= a; i++)
vis[i] = 1;
X = a + 1, Y = -1;
ans = 0;
}
void solve1(int x) {
vis[x] = buy[x] = 1;
while(vis[X]) X++;
}
void solve2(int x) {
if(d == 1) { flag = 1; return; }
vis[x] = 0;
Q.push(x);
while(!vis[X - 1]) X--;
}
void solve3() {
if(d == 1 || Q.empty()) { flag = 1; return; }
int x = Q.front(); Q.pop();
vis[x] = 1;
while(vis[X]) X++;
}
int main() {
T = read();
while(T--) {
init();
for(int i = 1; i <= m; i++) {
flag = 0;
if(p[i] == -1) solve3();
else if(p[i] > a && !buy[p[i]]) solve1(p[i]);
else if(vis[p[i]]) solve2(p[i]);
else solve3();
if(flag) continue;
Y = Q.min_ele();
cur = (Y == -1 ? X : min(X, Y));
update_ans(ans, cur, i);
}
write(ans), putchar('\n');
}
return 0;
}
线性函数
给定 $n$ 个线性函数，其中 $f_i(x)=k_i x + b_i$。有 $m$ 次操作，每次操作分为两种类型：
$\verb!M i K B!$ ： $k_i\gets K,b_i\gets B$
$\verb!Q l r x!$ : 求 $f_r(f_{r-1}(\cdots f_l(x))))$
$n,m\leq 2\times 10^5$
题解
可以发现，线性函数的迭代具有结合性，且线性函数的迭代也是线性函数。
那么可以用线段树维护，线段树上的节点储存其代表区间的 $k$ 和 $b$，则节点 $\text{L}(k_l,b_l)$ 和节点 $\text{R}(k_r,b_r)$ 的和为 $\text{P}(k_l\cdot k_r, k_r \cdot b_l + b_r)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
inline bool read_op() {...}
const int MAX_N = 2e5 + 10, MOD = 1e9 + 7;
int n, m;
struct node {
int k, b;
node(int _k = 1, int _b = 0) :
k(_k), b(_b) {}
node operator + (const node &t) const { return node(1ll * k * t.k % MOD, (1ll * t.k * b % MOD + t.b) % MOD); }
} d[MAX_N << 2];
inline int lc(int p) { return (p << 1); }
inline int rc(int p) { return (p << 1) | 1;}
inline void pu(int p) { d[p] = d[lc(p)] + d[rc(p)]; }
void update(int p, int s, int t, int pos, int k, int b) {
if(s == t) { d[p] = node(k, b); return; }
int mid = (s + t) >> 1;
if(pos <= mid) update(lc(p), s, mid, pos, k, b);
else update(rc(p), mid + 1, t, pos, k, b);
pu(p);
}
node query(int p, int s, int t, int l, int r) {
if(l <= s && t <= r) return d[p];
int mid = (s + t) >> 1;
node ret;
if(l <= mid) ret = ret + query(lc(p), s, mid, l, r);
if(r > mid) ret = ret + query(rc(p), mid + 1, t, l, r);
return ret;
}
int main() {
n = read(), m = read();
for(int i = 1, k, b; i <= n; i++) {
k = read(), b = read();
update(1, 1, n, i, k, b);
}
while(m--) {
int op = read_op();
if(op == 0) {
int i = read(), k = read(), b = read();
update(1, 1, n, i, k, b);
}
else {
int l = read(), r = read(), x = read();
node t = query(1, 1, n, l, r);
write((1ll * t.k * x % MOD + t.b) % MOD);
putchar('\n');
}
}
}
[DMOI-R2] 梦境
小 A 的梦境可以看做有 $n$ 个点，$m$ 条边的无向图。小 A 在图上的点 $S$，有一个怪物在点 $B$，安全屋在点 $F$。
怪物正在追杀小 A，现在小 A 需要逃到安全屋。小 A 意识到这是在自己的梦境里，所以他在一定程度上操控了梦境。他把怪物的移动速度设置成了 $3$，但代价是自己的移动速度被设置成 $2$。
小 A 始终会沿着到 $F$ 的最短路走，如果有多条最短路，则小 A 会选择使得经过点的编号所顺次构成序列的字典序最小的那条最短路，因为他觉得这样走最不容易被怪物抓到。
而怪物在梦境中游荡，会随机向自身周围的点移动，且怪物已经访问过的点不会重复访问。
现在小 A 需要知道在最坏情况下他能否安全到达安全屋，或者何时被怪物抓住。
$S \ne B \ne F$ 且 $1 \le S,B,F \le n$，$1 \le w_i \le 10^3$
题解
在本题中，我们显然需要找到并记录小 A 所走的那条字典序最小的最短路，这是小 A 的固定路线。
要使字典序最小，我们从 $F$ 开始倒着做 dijkstra 算法。同时记录每一个点的前驱，就能求出 $S$ 到 $T$ 的路径。设 $dis_1(u)$ 为 $u$ 到 $S$ 的最短距离。
对于怪物来说，它要先到达小 A 的路径，再与小 A 做追及或相遇的运动。所以，我们也需要求出 $B$ 点的单源最短路。设 $dis_2(u)$ 为 $u$ 到 $B$ 的最短距离。
之后只要枚举小 A 路径上的每一个点 $u$，比较小 A 和怪物谁先到达这个点，即比较 $T_1=\frac{dis_1(u)}{2}$ 与 $T_2=\frac{dis_2(u)}{3}$ 的大小。
如果小 $A$ 先到，则怪物到达这个点的时候小 A 已经往前走了，这个时候怪物做追及运动，他们之间的相对距离 $\Delta=T_2\cdot 2 -dis_1(u)$。则追上的用时 $t=T_2 +\Delta$。
反之做相遇运动，他们之间的相对距离 $\Delta=dis_1(u)-T_2\cdot 2$。则追上的用时 $t=T_2 +\frac{\Delta}{5}$。
我们将 $\min(t)$ 与 $\frac{dis_1(F)}{2}$ 比较，即可算出是否能追上。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 2e5 + 10, INF = (1 << 30);
int n, m, S, B, F, tot, cnt;
int pre[MAX_N], fir[MAX_N], dis1[MAX_N], dis2[MAX_N], path[MAX_N];
bool vis[MAX_N];
struct edge {
int v, w, nxt;
edge() { }
edge(int _v, int _w, int _nxt) :
v(_v), w(_w), nxt(_nxt) { }
} E[MAX_N << 1];
inline void AddEdge(int u, int v, int w) {
E[++tot] = edge(v, w, fir[u]);
fir[u] = tot;
}
void dijkstra(int s, int *dis, bool flag) {
priority_queue<pii, vector<pii>, greater<pii>> pq;
for(int i = 1; i <= n; i++)
vis[i] = 0, dis[i] = INF;
dis[s] = 0;
pq.push(make_pair(0, s));
while(!pq.empty()) {
int u = pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = fir[u]; i; i = E[i].nxt) {
int v = E[i].v, w = E[i].w;
if(flag) {
if(dis[u] + w == dis[v]) pre[v] = min(pre[v], u);
else if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
pre[v] = u;
pq.push(make_pair(dis[v], v));
}
}
else if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
pq.push(make_pair(dis[v], v));
}
}
}
}
int main() {
n = read(), m = read(), S = read(), B = read(), F = read();
for(int i = 1, u, v, w; i <= m; i++) {
u = read(), v = read(), w = read();
AddEdge(u, v, w);
AddEdge(v, u, w);
}
dijkstra(F, dis1, 1);
dijkstra(B, dis2, 0);
int now = S, td = dis1[S];
while(now) {
path[++cnt] = now;
dis1[now] = td - dis1[now];
now = pre[now];
}
ld ori, tim;
ori = tim = td / 2.0;
while(cnt) {
now = path[cnt--];
ld Time = dis2[now] / 3.0;
if(dis1[now] / 2.0 >= dis2[now] / 3.0) tim = min(tim, Time + (dis1[now] - Time * 2) / 5);
else tim = min(tim, Time + (Time * 2 - dis1[now]));
}
cout.precision(15);
if(tim == ori && dis2[F] / 3.0 != ori) {
ld ans = dis2[F] - tim * 3;
cout << "YES" << endl << ans;
}
else cout << "NO" << endl << tim;
return 0;
}
♥