各种优化建图、最短路建模技巧

废物才会开启防护 發表於 2025-7-14 21:02:00

直接看题吧，思路有了，但是有些题代码没打。兔子正在加油中。
<h1 id="优化建图">优化建图</h1>
<h2 id="i线段树cf786b-legacy">I.（线段树）CF786B Legacy</h2>
<details>
<summary>题目描述</summary>
三种连边操作，执行 $q(1\le n\le10^5)$ 次：
<ul>
<li>$x\xrightarrow{w}y$</li>
<li>$x\xrightarrow{w}y,y\in$</li>
<li>$x\xrightarrow{w}y,x\in$</li>
</ul>
求 $s$ 到其余点的最短路。
</details>
暴力连边肯定不行。 
有没有什么东西是把一个区间拆分成 $\log$ 个的？
当然是线段树优化建图啦。因为加入的是一个区间，所以用线段树上的 $\log$ 个结点来表示区间，对这些结点连边。 
对于 $ \to v$，把 $\log$ 个结点连向线段树上的 $v$，之后把线段树本身连成一颗内向树。 
对于 $ \gets v$，在对线段树内部连边时，显然不能和上一种情况连同一些结点，不然最短路都是 $0$。于是重新开一颗线段树，把这个颗树连成外向树。对于这颗线段树上的 $\log$ 个结点，连向上内向树上的 $v$。 
这两颗树上的叶子在原图上是同一个点，所以这两颗树的叶子要连权值为 $0$ 的边（显然只需要外向树向内向树连边）。 
对于建出来的图跑最短路，有 $n$ 个结点 $m\log n$ 条边，堆优化 Dijkstra 时间复杂度 $\mathcal{O}(m\log_2 n)$。
<details>
<summary>CF786B</summary>
<pre><code class="language-cpp">
/*
author: Nimbunny
powered by c++14
*/

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pi pair<int,int>

using namespace std;
const int N=3e6+10,K=5e5;
int n, m, s, op, a, d;
bool vis;
priority_queue<pi> q;

int pre, cnt;
struct node{
int to, next, l;
}g;

void add(int u,int v,int l){
g[++cnt] = {v, pre, l};
pre = cnt;
return ;
}

struct Segment_Tree{
#define ls (k << 1)
#define rs (ls | 1)
void build(int k, int l, int r){
 if(l == r) return a = k, void();
 int mid = l + r >> 1;
 add(k, ls, 0);
add(k, rs, 0);
 add(ls + K, k + K, 0);
add(rs + K, k + K, 0);
 build(ls, l, mid);
 build(rs, mid+1, r);
}
void modify(int k, int l, int r, int lx, int rx, int v, int w){
 if(l >= lx && r <= rx){
 if(op == 2) add(v + K, k, w);
 else add(k + K, v, w);
 return ;
 }
 int mid = l + r >> 1;
 if(lx <= mid) modify(ls, l, mid, lx, rx, v, w);
 if(rx > mid) modify(rs, mid+1, r, lx, rx, v, w);
 return ;
}
}tree;

inline void dijkstra(int s){
memset(d, 0x3f, sizeof d);
d = 0;
q.push(make_pair(0, s));
while(q.size()){
 int x = q.top().second;
q.pop();
 if(vis) continue;
 vis = true;
 for(int i = pre; i; i = g.next){
 int to = g.to, l = g.l;
 if(d > d + l) {
d = d + l;
q.push(make_pair(-d, to));
}
 }
}
return ;
}

inline int read(){
int x;
cin >> x;
return x;
}

signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
n = read(), m = read(), s = read();
tree.build(1, 1, n);
for(int i = 1; i <= n; i++){
 add(a, a + K, 0);
add(a + K, a, 0);
}
for(int i = 1; i <= m; i++){
op = read();
 if(op==1){
int x = read(), y = read(), z = read();
add(a + K, a, z);
}else{
 int x = read(), l = read(), r = read(), w = read();
 tree.modify(1, 1, n, l, r, a, w);
 }
}
dijkstra(a + K);
for(int i = 1;i <= n; i++){
if(d] == 0x3f3f3f3f3f3f3f3f) cout << -1 << " ";
else cout << d] << " ";
}
return 0;
}
</code></pre>
</details>
<h2 id="ii-后缀树p5284-十二省联考-2019-字符串问题">II. （后缀树）P5284 [十二省联考 2019] 字符串问题</h2>
用后缀树优化建图，然后跑 DAG 上 DP。
<details>
<summary>P5284</summary>
<pre><code class="language-cpp">
/*
author: Nimbunny
powered by c++14
*/

#include <bits/stdc++.h>
#define endl '\n'
#define pb emplace_back
#define all(x) x.begin(), x.end()
#define rev(x) reverse(all(x))
#define mem(x, v) memset(x, v, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof y)
#define ll long long
#define vint vector<int>

using namespace std;
const int N = 4e5 + 5;
const int S = 26;
const int inf = 1e9 + 7;

// Segtree_Min
int deg, val, laz;
void up(int x) {
val = min(val, val);
}
void down(int x) {
if (laz) {
 val -= laz, val -= laz;
 laz += laz, laz += laz;
}
laz = 0;
}
void build(int l, int r, int x) {
laz = val = 0;
if (l == r) return val = deg, void();
int m = l + r >> 1;
build(l, m, x << 1), build(m + 1, r, x << 1 | 1), up(x);
}
void modify(int l, int r, int ql, int qr, int x) {
if (ql <= l && r <= qr) return val--, laz++, void();
int m = l + r >> 1;
down(x);
if (ql <= m) modify(l, m, ql, qr, x << 1);
if (m < qr) modify(m + 1, r, ql, qr, x << 1 | 1);
up(x);
}
int query(int l, int r, int x) {
if (l == r) return val = inf, l;
int m = l + r >> 1, ans;
down(x);
if (!val)
 ans = query(l, m, x << 1);
else
 ans = query(m + 1, r, x << 1 | 1);
return up(x), ans;
}

// SegTree_Max
ll ini, val2, laz2;
void cmax(ll &x, ll y) {
x = max(x, y);
}
void up2(int x) {
val2 = max(val2, val2);
}
void down2(int x) {
if (laz != -1) {
 cmax(laz2, laz2), cmax(laz2, laz2);
 cmax(val2, laz2), cmax(val2, laz2);
}
laz2 = -1;
}
void build2(int l, int r, int x) {
val2 = laz2 = -1;
if (l == r) return val2 = ini, void();
int m = l + r >> 1;
build2(l, m, x << 1), build2(m + 1, r, x << 1 | 1), up2(x);
}
void modify2(int l, int r, int ql, int qr, int x, ll v) {
if (ql <= l && r <= qr)
 return cmax(val2, v), cmax(laz2, v), void();
int m = l + r >> 1;
down2(x);
if (ql <= m) modify2(l, m, ql, qr, x << 1, v);
if (m < qr) modify2(m + 1, r, ql, qr, x << 1 | 1, v);
up2(x);
}
ll query2(int l, int r, int p, int x) {
if (l == r) return val2;
int m = l + r >> 1;
down2(x);
if (p <= m) return query2(l, m, p, x << 1);
return query2(m + 1, r, p, x << 1 | 1);
}

// Suffix_Automaton
int n, K, cnt, las;
int fa, len, ed, son, ff;
vint FAIL;
void ins(char s) {
int p = las, cur = ++cnt, it = s - 'a';
len = len + 1, ed] = cur, las = cur;
while (p && !son) son = cur, p = fa;
if (!p) return fa = 1, void();
int q = son;
if (len + 1 == len) return fa = q, void();
int cl = ++cnt;
fa = fa, fa = fa = cl, len = len + 1;
mcpy(son, son);
while (son == q) son = cl, p = fa;
}
void build(char *s) {
for (int i = 1; i <= n; i++) ins(s);
for (int i = 2; i <= cnt; i++)
 FAIL].pb(i), ff = fa;
K = log2(cnt);
for (int i = 1; i <= K; i++)
 for (int j = 1; j <= cnt; j++)
 ff = ff];
}
int getpos(int l, int r) {
int p = ed;
for (int i = K; ~i; i--)
 if (r - len] + 1 <= l) p = ff;
return p;
}

char s;
int na, nb, tot, m;
int dnum, lens, tmp, rev, id, sz;
vint DAG, tag;

bool cmp(int a, int b) {
return lens != lens ? lens < lens : a > b;
}
int dfs(int d) {
int z = tag.size(), l = dnum + 1, r = dnum + z;
sort(all(tag), cmp);
for (int it : tag) id = ++dnum;
for (int it : FAIL) z += dfs(it);
for (int i = l; i <= r; i++) sz = z - (i - l);
return z;
}

void clear() {
// clear SAM
for (int i = 1; i <= cnt; i++)
 mem(son, 0), mem(ff, 0), ed = len = fa = 0;
// clear Fail tree
for (int i = 1; i <= cnt; i++) FAIL.clear(), tag.clear();
for (int i = 1; i <= tot + 1; i++)
 lens = id = sz = deg = 0;
// clear DAG
for (int i = 1; i <= na; i++) DAG.clear();
// clear variables
las = cnt = 1, dnum = na = nb = tot = 0;
}

inline int read() {
int x;
cin >> x;
return x;
}

void init() {
cin >> s + 1 >> na;
n = strlen(s + 1);
reverse(s + 1, s + n + 1), build(s);
for (int i = 1; i <= na; i++) {
 int l = read(), r = read();
 l = n - l + 1, r = n - r + 1, swap(l, r), lens = r - l + 1;
 tag.pb(i);
}
nb = read(), tot = na + nb;
for (int i = 1; i <= nb; i++) {
 int l = read(), r = read();
 l = n - l + 1, r = n - r + 1, swap(l, r),
 lens = r - l + 1;
 tag.pb(i + na);
}
m = read();
for (int i = 1; i <= m; i++) {
 int x = read(), y = read();
 DAG.pb(y + na);
}
dfs(1);
for (int i = 1; i <= tot; i++) tmp] = lens;
for (int i = 1; i <= tot; i++) lens = tmp, rev] = i;
}

queue<int> q;
bool update() {
if (val) return 0;
int p = query(1, tot, 1);
return ini = 0, q.push(p), 1;
}
bool calc_deg() {
for (int i = 1; i <= na; i++)
 for (int it : DAG) {
 int l = id, r = l + sz - 1;
 if (l <= id && id <= r) return 1;
 deg++, deg--;
 }
for (int i = 1; i <= tot; i++) deg += deg;
for (int i = na + 1; i <= tot; i++) deg] = inf;
return build(1, tot, 1), 0;
}
ll topo() {
for (int i = 1; i <= tot; i++) ini = -1;
while (update());
build2(1, tot, 1);
ll ans = 0;
while (!q.empty()) {
 ll t = q.front(), v = query2(1, tot, t, 1) + lens;
 q.pop();
 cmax(ans, v);
 for (int it : DAG]) {
 int l = id, r = l + sz - 1;
 modify(1, tot, l, r, 1), modify2(1, tot, l, r, 1, v);
 while (update());
 }
}
return val < 1e6 ? -1 : ans;
}

inline void solve() {
clear(), init();
if (calc_deg()) return puts("-1"), void();
cout << topo() << endl;
return;
}
signed main() {
int _ = read();
while (_--) solve();
return 0;
}
</code></pre>
</details>
<h2 id="iii倍增-or-st表--虚点p5344-xr-1逛森林">III.（倍增 or ST表 + 虚点）P5344 【XR-1】逛森林</h2>
解法 $1$：
区间向区间连边，转化为区间向虚点连边，虚点向区间连边。
倍增优化建图，与线段树类似，只不过放到了树上。需要建出两个倍增树，一个管理出边，一个管理入边。时间复杂度为 $\mathcal{O}(m\log n\log(m\log n))$。
解法 $2$： 
可以将树通过 dfs 序拍到序列上，并使用 ST 表维护连边。具体地，可以将 拆成 ，其中 $k$ 为 $\lfloor\log_2(r-l+1)\rfloor$，因为重复连边不影响最终的答案。时间复杂度 $\mathcal{O}(m\log m)$。
<details>
<summary>P5344</summary>
<pre><code class="language-cpp">// Problem: P5344 【XR-1】逛森林
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5344
// Memory Limit: 500 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
author: Nimbunny
powered by c++14
*/

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define pi pair<int, int>
#define fi first
#define se second
#define gc getchar()

using namespace std;

const int N = 5e4 + 5;
const int K = 16;
const int M = 1e6 + 5;
const int T = N * K * 2 + M;

inline int read() {
int x;
cin >> x;
return x;
}

int f;

int find(int x) {
return f == x ? x : f = find(f);
}

bool same(int u, int v) {
return find(u) == find(v);
}

bool merge(int u, int v) {
u = find(u), v = find(v);
return f = v, u != v;
}

struct operation {
int u1, v1, u2, v2, w;
void rd() {
 u1 = read(), v1 = read(), u2 = read(), v2 = read(),
 w = read();
}
} p;

int n, m, s, k, cnt, node;
vector<pi> e;

int vis, dep, fa, in, out;

void dfs(int x, int f, int d) {
vis = 1, fa = f, in = x, out = x + n,
dep = d;
for (pi it : e)
 if (it.fi != f) dfs(it.fi, x, d + 1);
}

void con(int u, int v, int p, int w, int tp) {
if (dep < dep) swap(u, v);
for (int i = k; ~i; i--)
 if (dep] >= dep) {
 if (tp)
 e].pb({p, w});
 else
 e.pb({in, w});
 u = fa;
 }
for (int i = k; ~i; i--)
 if (fa != fa) {
 if (tp)
 e].pb({p, w}), e].pb({p, w});
 else
 e.pb({in, w}), e.pb({in, w});
 u = fa, v = fa;
 }
if (u != v) {
 if (tp)
 e].pb({p, w}), e].pb({p, w});
 else
 e.pb({in, w}), e.pb({in, w});
 u = fa, v = fa;
}
if (tp)
 e].pb({p, w});
else
 e.pb({in, w});
return;
}

int dis;
priority_queue<pi, vector<pi>, greater<pi> > q;
void dijkstra(int s) {
memset(dis, 0x3f, sizeof dis);
dis = 0, q.push({0, s});
while (!q.empty()) {
 pi t = q.top();
 q.pop();
 int id = t.se, ds = t.fi;
 if (dis < ds) continue;
 for (pi it : e)
 if (dis > ds + it.se)
 q.push({dis = ds + it.se, it.fi});
}
}

signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> s;
node = n << 1, k = log2(n);
for (int i = 1; i <= n; i++) f = i;
for (int i = 1; i <= m; i++) {
 int tp = read();
 if (tp == 1) {
 operation t;
 t.rd();
 if (same(t.u1, t.v1) && same(t.u2, t.v2)) p[++cnt] = t;
 } else {
 int u = read(), v = read(), w = read();
 if (merge(u, v)) e.pb({v, w}), e.pb({u, w});
 }
}
for (int i = 1; i <= n; i++)
 if (!vis) dfs(i, 0, 1);
for (int i = 1; i <= n; i++)
 e.pb({i + n, 0}), e.pb({i, 0});
for (int i = 1; i <= k; i++)
 for (int j = 1; j <= n; j++)
 in = ++node, e.pb({in, 0}),
 e.pb({in], 0}),
 out = ++node, e].pb({node, 0}),
 e]].pb({node, 0}),
 fa = fa];
for (int i = 1; i <= cnt; i++)
 con(p.u1, p.v1, ++node, p.w, 1),
 con(p.u2, p.v2, node, 0, 0);
dijkstra(s);
for (int i = 1; i <= n; i++)
 cout << (dis < 1e8 ? dis : -1) << " ";
return 0;
}
</code></pre>
</details>
<h2 id="iv线段树--虚点p1983-noip-2013-普及组-车站分级">IV.（线段树 + 虚点）P1983 车站分级</h2>
解法 $1$（暴力）： 
对于一条线路 $t_1\to t_2\to\dots\to t_s$，将所有编号在该线路之间却没有经过的站点 $p(\in$ 且 $p\ni{t_i}$ 向所有经过的站点 $t_i$ 连一条边 $p\to t_i$ 表示 $p$ 的编号一定小于 $t_i$，然后跑拓扑排序即可。一次连边 $\mathcal{O}(n^2)$，总时间 $\mathcal{O}(n^2m)$。
解法 $2$（虚点）： 
根据例题 III. 可知区间向区间连边可以用虚点优化。需要注意最终答案要除以 $2$，因为点到虚点再到点的长度为 $2$，而实际上应该为 $1$。时间复杂度 $\mathcal{O}(nm)$。
<details>
<summary>P1983</summary>
<pre><code class="language-cpp">// Problem: P1983 车站分级
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1983
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
author: Nimbunny
powered by c++14
*/

#include <bits/stdc++.h>
#define endl '\n'
#define pi pair<int, int>

using namespace std;
const int INF = INT_MAX;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;
int n, m, node, t, deg, f;
bool buc;
vector<int> e;

signed main() {
cin >> n >> m, node = n;
for (int i = 1, s; i <= m; i++) {
 memset(buc, false, sizeof buc);
 cin >> s;
 for (int i = 1; i <= s; i++) cin >> t, buc] = true;
 if (t - t + 1 == s) continue;
 node++;
 for (int i = t; i <= t; i++)
 if (buc)
 e.push_back(i), deg++;
 else
 e.push_back(node), deg++;
}
queue<int> q;
for (int i = 1; i <= node; i++)
 if (!deg) q.push(i);
while (!q.empty()) {
 int t = q.front();
 q.pop();
 for (int v : e) {
 f = max(f, f + 1);
 if (!--deg) q.push(v);
 }
}
int ans = 0;
for (int i = 1; i <= node; i++) ans = max(ans, f);
cout << ans / 2 + 1 << endl;
return 0;
}
</code></pre>
</details>
解法 $3$（线段树 + 虚点）： 
点与区间的连边用线段树优化即可。最后跑拓扑也在线段树上跑。时间复杂度 $\mathcal{O}(m\log n)$。
<h1 id="最短路建模">最短路建模</h1>
<h2 id="p9351-迷宫--maze">P9351 迷宫 / Maze</h2>
<details>
<summary>题目描述</summary>
给一个 $r\times c$ 的网格图，有一些障碍物。每次操作可以打通一个 $n\times n$ 的正方形，求将输入的起点和终点四联通的最小操作步数。$1\le n\le r\le c,r\times c\le6\times10^6$。
</details>
考虑把打通的代价和变化表示出来，那么就是选择打通就要 $1$ 的代价，然后可以走 $n\times n$ 的 $0$ 权边。但是给每个点新建一个 $n\times n$ 的 $0$ 权图复杂度太大，能不能只建立一个辅助图，同时在这个图上限制只能走 $n\times n$。 
如果将一个正方形打通，则可以再上面不管障碍物地乱走，然后在某个地方走出去。所以有三种情况：不管障碍物、管障碍物、随便走不管障碍物。 
所以考虑建立两个图，第一个图是原图，上面的 <code>.</code> 都可以走。第二个图描述 $n\times n$ 的覆盖，八联通，边权都为 $1$，限制一次走的边权小于 $n$。然后第一个图的点可以四联通的走到第二个图上，代价为$1$。那么相当于双关键字最短路，两张图也没必要真的建出来，第二个关键字跑满再走第一个关键字，这样就能01bfs了。
<details>
<summary>P9351</summary>
<pre><code class="language-cpp">
/*
author: Nimbunny
powered by c++14
*/

#include <bits/stdc++.h>
#define endl '\n'
#define pi pair<int,int>

using namespace std;
const int dx4 = {-1, 0, 0, 1};
const int dy4 = {0, -1, 1, 0};
const int dx8 = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8 = {-1, 0, 1, -1, 1, -1, 0, 1};
const int N = 6e6 + 10;
int n, m, k, sx, sy, tx, ty;
bool a, vis;

inline int read(){
int x;
cin >> x;
return x;
}

inline bool check(int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= m);
}

inline int id(int x, int y) {
return (x - 1) * m + y;
}

struct node {
int x, y, t, h;
};

int main() {
cin.tie(nullptr)->sync_with_stdio(false);
n = read(), m = read(), k = read();
sx = read(), sy = read(), tx = read(), ty = read();
for (int i = 1; i <= n; i++) {
 string s;
 cin >> s;
 for (int j = 1; j <= m; j++)
 a = (s == '#');
}
deque<node> q(1, {sx, sy, 0, 0});
while (1) {
 node top = q.front();
 q.pop_front();
 int x = top.x;
 int y = top.y;
 int t = top.t;
 int h = top.h;
 if (vis) continue;
 vis = true;
 if (x == tx && y == ty)
 return cout << t << endl, 0;
 if (h) {
 for (int d = 0; d <= 7; d++) {
 int xx = x + dx8;
 int yy = y + dy8;
 if (check(xx, yy) && !vis)
 q.push_back({xx, yy, t, h-1});
 }
 } else {
 for (int d = 0; d <= 3; d++) {
 int xx = x + dx4;
 int yy = y + dy4;
 if (check(xx, yy) && !vis) {
 if (a)
 q.push_back({xx, yy, t + 1, k - 1});
 else
 q.push_front({xx, yy, t, 0});
 }
 }
 }
}
return 0;
}
</code></pre>
</details>
<h2 id="arc084b">ARC084B</h2>
<details>
<summary>题目描述</summary>
给定一个整数 $K$，求一个 $K$ 的正整数倍 $S$，使得 $S$ 的数位累加和最小。$2\le K\le105$。
</details>
直接做倍数之类的不太好做。注意到 $K$ 很小，可以考虑 $\mod K = 0$ 就是 $K$ 的倍数，从 $\mod K$下手。
<ul>
<li>考虑从 $1$ 开始，通过 $\times 10$ 和 $+1$ 同时不进位凑一个 $K$ 的倍数，这一定可以做到。</li>
<li>$\times 10$ 对数位和的贡献为 $0,+1$ 的贡献为 $1$，判断是否为倍数只需要考虑 $\mod K$ 是否为 $0$。</li>
<li>建立一个图（不需要真的建）：
<ul>
<li>$x\xrightarrow{0} x\times10\mod K$</li>
<li>$x\xrightarrow{1} (x+1) \mod K$</li>
</ul>
</li>
<li>跑01bfs求出最短路即为答案。</li>
</ul>
<details>
<summary>ARC084B</summary>
<pre><code class="language-cpp">
/*
author: Nimbunny
powered by c++14
*/

#include <bits/stdc++.h>
#define endl '\n'
#define pi pair<int, int>

using namespace std;
const int INF = INT_MAX;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int k, dis;
bool vis;
vector<pi> g;
deque<int> q;

inline int read() {
int x;
cin >> x;
return x;
}

int main() {
cin.tie(nullptr)->sync_with_stdio(false);
k = read();
for (int i = 0; i <= k - 1; i++) {
 g.push_back({(i + 1) % k, 1});
 g.push_back({(i * 10) % k, 0});
}
memset(dis, 0x3f, sizeof dis);
dis = 1;
q.push_back(1);
while (!q.empty()) {
 int x = q.front();
 q.pop_front();
 if (vis) continue;
 vis = true;
 for (pi i : g) {
 int y = i.first, w = i.second;
 if (dis > dis + w) {
 dis = dis + w;
 if (!w)
 q.push_front(y);
 else
 q.push_back(y);
 }
 }
}
cout << dis << endl;
return 0;
}
</code></pre>
</details>
<h2 id="p7297-usaco21jan-telephone-g">P7297 Telephone G</h2>
<details>
<summary>题目描述</summary>
$n$ 头奶牛，一共 $K$ 种，第 $i$ 头奶牛品种是 $b_i$。给定一个 $K\times K$ 的矩阵 $S$，如果 $S_{i,j}=1$ 表示第 $i$ 种奶牛和第 $j$ 种之间可以交流，第 $i$ 头奶牛和第 $j$ 头之间需要 $\midi−j\mid$ 的时间交流。求 $1\to n$ 交流的需要的时间。$1\le n\le5\times10^4,1\le K\le50$。
</details>
需要刻画哪些奶牛能交流。先把绝对值拆开，然后真的需要每个奶牛都连边吗？ 
直接建图是 $\mathcal{O}(n^2)$ 的，注意到 $k$ 很小。对每种奶牛建立一张新图，每张图内部按照位置排序，相邻的奶牛之间连边。同时保留一张原图，原图是 $n$ 只奶牛，之间不连边。对于一只奶牛 $x$，枚举它能走到的哪种奶牛，找到位置小于它的最大的和大于的最小的该种奶牛 $y_1,y_2$，连接 $x$ 原图和 $y_1,y_2$ 新图。不难证明任意两只能互达的奶牛 $i,j$ 之间的最短路等于 $\mid i − j\mid$。 
图的点数为 $\mathcal{O}(n)$，边数为 $\mathcal{O}(nk)$，跑 Dijkstra 即可。
<details>
<summary>P7297</summary>
<pre><code class="language-cpp">
/*
author: Nimbunny
powered by c++14
*/

#include<bits/stdc++.h>
#define endl '\n'
#define pi pair<int,int>

using namespace std;
const int N = 5e4 + 10, M = 2e6 + 10;
char s;
int d,rad;
int v,tot;
int n,k,a;
bool vis;
priority_queue<pi>q;

inline int read(){
int x;
cin>>x;
return x;
}

void dijkstra(){
memset(d,0x3f,sizeof d);
d=0;
q.push(make_pair(0,1));
while(!q.empty()){
int x=q.top().second;
q.pop();
if(vis) continue;
vis=true;
if(x==n) break;
for(int i=1;i<=k;i++)
if(rad])
for(int j=1;j<=tot;j++){
int y=v;
while(vis&&tot>1){
swap(v,v]);
tot--;
y=v;
if(tot==1) break;
}
if(!vis&&(d>d+abs(y-x))){
d=d+abs(y-x);
q.push(make_pair(-d,y));
}
}
}
return ;
}

signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
n=read(),k=read();
for(int i=1;i<=n;i++)
v=read()][++tot]]=i;
for(int i=1;i<=k;i++){
cin>>s+1;
for(int j=1;j<=k;j++)
if(s=='1')
rad=1;
}
dijkstra();
if(d==0x3f3f3f3f)
return cout<<-1<<endl,0;
cout<<d<<endl;
return 0;
}
</code></pre>
</details>
<h2 id="p4366-code4-最短路">P4366 最短路</h2>
<details>
<summary>题目描述</summary>
共 $n$ 个点，$i\xrightarrow{(i\oplus j)\times C}j$，另有 $m$ 条有向边，求 $a\to b$ 的最短路。
</details>
异或的每一位是独立的，可以拆开？ 
考虑把异或边权拆开，$i$ 向 $i \oplus 2^j$ 连边权 $2^j\times C$ 的边（$i\oplus 2^j\le n$）。 
然后直接对这 $n\log n+m$ 条边跑最短路即可。
<details>
<summary>P4366</summary>
<pre><code class="language-cpp">
</code></pre>
</details>
<h2 id="at_abc164_e-two-currencies">AT_abc164_E Two Currencies</h2>
<details>
<summary>题目描述</summary>
有 $n(1\le n\le50)$ 个城市，由 $m(n-1\le m\le 100)$ 条双向道路连接，保证连通。第 $i$ 条道路连接 $u_i,v_i$，需要花费 $x_i(1\le x_i\le 50)$ 个银币，耗费 $t_i(1\le t_i\le 10^9)$ 秒的时间。 
每个城市处都有兑换银币处，第 $i$ 个城市中你可以用 $1$ 个金币和 $d_i(1\le d_i\le 10^9)$ 秒时间兑换 $c_i(1\le c_i\le10^9)$ 个银币，可以兑换无限次。 
你有 $s(1\le s\le10^9)$ 个银币和无限多的金币，求 $1$ 到其他城市的最少时间。
</details>
发现 $1\le n\le 50$ 非常奇怪。 
设 $d_{i,j}$ 为在点 $i$ 有 $j$ 个银币的最短路，由于 $\displaystyle\sum_{i=1}^{n} xi ≤ 49 \times 50$，所以 $j \le 2450$，如果超过了 $2450$ 也看作 $2450$ 因为已经足够了。 
然后在 $d_{i,j}$ 之间连边，也就是跑分层图最短路，也是非常巧的。
<details>
<summary>AT_abc164_E</summary>
<pre><code class="language-cpp">
/*
author: Nimbunny
powered by c++14
*/

#include <bits/stdc++.h>
#define endl '\n'
#define pi pair<int,int>
#define pii pair<int,pi>
#define int long long

using namespace std;
const int N = 60, M = 2510;

struct AC {
int v, x, b;
};

int n, m, s;
int dist;
vector<AC> g;

void dijkstra() {
memset(dist, 0x3f, sizeof dist);
priority_queue<pii, vector<pii>, greater<pii> > q;
q.push({0, {1, min(2500ll, s)}});
dist = 0;
while(q.size()) {
auto p = q.top();
q.pop();
pi t = p.second;
int u = t.first, x = t.second;
if(p.first > dist) continue;
for(AC a : g) {
if(dist > dist + a.b) {
dist = dist + a.b;
q.push({dist, {a.v, a.x}});
}
}
}
return ;
}

inline int read() {
int x;
cin>>x;
return x;
}

signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
n = read(), m = read(), s = read();
while(m--) {
int u=read(), v=read(), a=read(), b=read();
for(int i = a; i <= 2500; i++) {
g.push_back({v, i - a, b});
g.push_back({u, i - a, b});
}
}
for(int u = 1; u <= n; u++) {
int c = read(), d = read();
for(int i = 0; i <= 2500; i++)
g.push_back({u, min(2500ll, i + c), d});
}
dijkstra();
for(int u = 2; u <= n; u++) {
int res = 1e18;
for(int i = 0; i <= 2500; i++) res = min(res, dist);
cout << res << endl;
}
return 0;
}
</code></pre>
</details>
<h2 id="p9370-apio2023-赛博乐园--cyberland">*P9370 赛博乐园 / cyberland</h2>
好题！建议看一下题目。
给定一张 $n$ 个点 $m$ 条边的无向图，经过第 $i$ 条边会用 $w_i$ 的时间。 
有些点在经过时可以选择改变总通过时间，多次经过可以多次改变，但是除以 $2$ 只能使用 $k$ 次。
<ul>
<li>$arr_i = 0$，经过这个点会使得总通过时间为 $0$。</li>
<li>$arr_i = 1$，不改变总通过时间。</li>
<li>$arr_i = 2$，经过这个点会使得总通过时间为 $\frac{\text{总时间}}{2}$。</li>
</ul>
保证 $arr_0 = arr_H = 1$，求 $0 \to H$ 的最短通过时间。 
交互，多组询问，$2\le n,\displaystyle\sum_{i=1}^{n}{n}\le10^5,0\le m\le\min(10^5,\frac{n(n-1)}2),\displaystyle\sum_{i=1}^{n}{m}\le10^5,1\le k\le 10^6,1\le c_i\le10^9$。
答案会是浮点数，所求答案与正确答案误差在 $1^{-6}$ 内即可，且有 $K \le 30$ 的部分分。
<hr>
首先把图反着跑，这样总通行时间除以 $2$ 就变成了后续时间都除以 $2$，当前总通过时间为 $0$ 就变成了后续时间都为 $0$。 
$K$ 很小，考虑用分层图来做，然后把一个点拆开成 $K+2$ 个，第 $i$ 个代表经过 $i$ 次除以二操作的点，最后一个代表经过清零操作的点，然后跑最短路。注意一下 $H$ 不能多次经过和不能达到为 $−1$，这样就有 $97$ 分了。
仔细想了一下，发现和 P4145 这题一样的思路可以说一样。P4145 是给一个区间开方，<s>显然用线段树</s>，但是一个小于 $10^9$ 的数开 $5$ 次方就已经是 $1$ 了，没有必要再开方了。而这道题，除以二的操作做 $\log_2{\frac{10^5\times 10^9}{10^{-6}}}\approx70$ 次就会变成可忽略值，所以 $K$ 和 $70$ 取最小的那一个就行。
<details>
<summary>P9370</summary>
<pre><code class="language-cpp">// Problem: P9370 赛博乐园 / cyberland
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9370
// Memory Limit: 2 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
author: Nimbunny
powered by c++14
*/

#include <bits/stdc++.h>

using namespace std;
const int INF = INT_MAX;
const int mod = 1e9+7;
const int N = 1e6 * 30 + 10;
int n, m, k, h;

int pre,cnt;
struct node {
int next, to;
double w, val;
} g;

struct ss {
int now;
double sum;
bool operator < (const ss &x) const {
 if (now / n != x.now / n) return now / n > x.now / n;
 return sum > x.sum;
}
};

bool vis;
double f;

inline void add(int u, int v, int w, double k) {
g[++cnt].to = v;
g.w = w;
g.val = (double)k;
g.next = pre;
pre = cnt;
return ;
}

void dfs(int now) {
vis = 1;
if (now == h) return ;
for (int i = pre; i; i = g.next)
 if (!vis.to] && g.val == 1)
 dfs(g.to);
return;
}

inline void init(int n,int k){
for (int i = 0; i <= (n + 1) * (k + 1); i++)
 vis = false, pre = 0, f = 1e24;
return ;
}

double solve(int N, int M, int K, int H, vector<int> x,
 vector<int> y, vector<int> c,
 vector<int> a) {
cnt = 0;
k = K = min(70, K); // 重点
n = N, m = M, h = H;
init(n,k);
for (int i = 0; i < M; i++) {
 for (int j = 0; j <= K; j++) {
 if (x != H) add(x + j * n, y + j * n, c, 1.0);
 if (y != H) add(y + j * n, x + j * n, c, 1.0);
 if (a] == 2 && y != H && j != k)
 add(y + j * N, x + (j + 1) * N, c, 2.0);
 if (a] == 2 && x != H && j != k)
 add(x + j * N, y + (j + 1) * N, c, 2.0);
 }
}
dfs(0);
if (!vis) return -1;
priority_queue<ss> q;
q.push({0, 0});
f = 0;
for (int i = 0; i < n; i++)
 if (a == 0 && vis)
 q.push({i, 0}), f = 0;
// dijkstra
for (int i = 0; i <= N + 1; i++) vis = false;
while (!q.empty()) {
 int t = q.top().now;
 q.pop();
 if (vis) continue;
 vis = true;
 for (int i = pre; i; i = g.next) {
 if (f.to] > (f + g.w) / g.val) {
 f.to] = (f + g.w) / g.val;
 if (!vis.to])
 q.push({g.to, f.to]});
 }
 }
}
double ans = 1e24;
for (int i = 0; i <= k; i++) ans = min(ans, f);
return ans;
}
</code></pre>
</details>
<h2 id="p6880-joi-2020-final-奥运公交--olympic-bus">P6880 奥运公交 / Olympic Bus</h2>
<details>
<summary>题目描述</summary>
给定一个 $n(2\le n\le200)$ 个点 $m(1\le m\le5\times10^4)$ 条边的有向图，可以选择或者不选一条边翻转方向，求 $1 \to n$ 的最短路加 $n \to 1$ 的最短路的和。
</details>
求出最短路树，枚举翻转那条边。 
如果翻转的是树边，重新跑最短路，树边只有 $\mathcal{O}(n)$ 条。 
如果翻转的是非树边 $x \to y$，最短路变为 
$\min(dis_{1,n} ,dis_{1,y} +w_{x,y} +dis_{x,n})+min(dis_{n,1},dis_{n,y} +w_{x,y} +dis_{x,1})$。 
证明显然，不存在经过 $x \to y$ 翻转后的更短的路径。
<details>
<summary>P6880</summary>
<pre><code class="language-cpp">
</code></pre>
</details>
<h2 id="p9724-ec-final-2022-chase-game">P9724 Chase Game</h2>
<details>
<summary>题目描述</summary>
Shou 教授被 Pang 教授在一个 $m(n-1\le m\le2\times10^5)$ 条边的无向无权简单图上追赶。最初，Shou 教授在顶点 $1$。他的目的地是顶点 $n(2\le n\le10^5)$。Pang 教授在顶点 $k(1\le k\le n)$。 
每秒钟，Shou 教授可以选择一个相邻的顶点并走向该顶点。然后，Shou 教授会受到 Pang 教授的攻击。此次攻击的伤害等于 $d-dis$，其中 $d(1\le d\le 2\times10^5)$ 是 Pang 教授的攻击范围，$dis$ 是图上从 Shou 教授到 Pang 教授的距离（最短路径上的边数）。然而，当 $dis$ 大于或等于 $d$ 时，Pang 教授无法造成任何正伤害。在这种情况下，他将会传送到 Shou 教授所在的顶点，然后造成 $d$ 伤害。（当 $dis$ 小于 $d$ 时，Pang 教授将停留在 
当前顶点） 
请找出 Shou 教授从顶点 $1$ 到顶点 $n$ 所需的最小伤害总和。Shou 教授将在顶点 $n$ 处受到最后一次攻击。
</details>
如果瞬移了一次，那么以后的伤害都是 $d,d − 1,\dots,1,d$，顺移到的都是之前走过的位置，如果距离没变，那么距离终点的最短路也没变，白吃了伤害。 
剩下的就是最开始距离小于 $d$ 的位置，对这些位置跑最短路。之后直接走到终点的最短路，此时已经瞬移了一次了。
<details>
<summary>P9724</summary>
<pre><code class="language-cpp">
/*
author: Nimbunny
powered by c++14
*/

#include<bits/stdc++.h>
#define int long long
#define pi pair<int, int>
#define xx first
#define yy second

using namespace std;
const int N = 1e5 + 10;
int n, m, k, d, dk, dn, ans = LLONG_MAX, dis;
vector<int> G;
bool vis;

int get(int l, int r){
return (l + r) * (r - l + 1) / 2;
}

int gs(int x){
return x / d * get(1, d) + get(d + 1 - x % d, d);
}

void bfs(int x, int *dis){
queue<int> q;
q.push(x);
memset(vis, 0, sizeof vis);
vis = 1;
while(!q.empty()){
 int u = q.front();
 q.pop();
 for(int v : G){
 if(!vis){
 vis = 1;
 q.push(v);
 dis = dis + 1;
 }
 }
}
return ;
}

void dij(int x){
priority_queue<pi, vector<pi>, greater<pi>> q;
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
dis = 0;
q.push({0, x});
while(!q.empty()){
 int u = q.top().yy;
 q.pop();
 if(vis)continue;
 vis = 1;
 for(int v : G){
 if(dk >= d)ans = min(ans, dis + gs(dn + 1));
 else if(dis + d - dk < dis){
 dis = dis + d - dk;
 q.push({dis, v});
 }
 }
}
return ;
}

inline int read(){
int x;
cin>>x;
return x;
}

signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
n = read(), m = read(), k = read(), d = read();
for(int i = 1; i <= m; i ++){
 int u = read(), v = read();
 G.push_back(v);
 G.push_back(u);
}
bfs(k, dk), bfs(n, dn), dij(1);
cout << min(ans, dis);
return 0;
}
</code></pre>
</details>
<h2 id="p5905-模板全源最短路johnson">P5905 【模板】全源最短路（Johnson）</h2>
<details>
<summary>题目描述</summary>
又一种全员最短路，但是有负权。
</details>
我们考虑使用 Dijkstra 来解决，但是 Dijkstra 不能处理有负权的图，考虑通过一些方法把图变为非负权图，再跑 $n$ 次 Dijkstra。 
新建一个虚点，向所有点连一条长度为 $0$ 的边，求出这个点到所有点的单源最短路。 
设虚点到 $u$ 的最短路为 $h_u$ ，对于一条 $x \to y$ 的边权为 $w$ 的边，边权改为 $w + h_x − h_y$ 。 
接下来跑 $n$ 次 Dijkstra 即可。 
时间复杂度瓶颈在于 Dijkstra，$\mathcal{O}(nm\log m)$。
从 $s$ 点到 $t$ 点的一条路径 $s \to p_1 \to p_2 \to \dots \to p_n \to t$ 的最短路
<div class="math display">\[(w_{s,p_1}+ h_s − h_{p_1} ) + (w_{p_1 ,p_2} + h_{p_1} − h_{p_2} ) + \dots + (w_{p_n ,t} + h_{p_n} − h_t )=w_{s,p_1} + w_{p_1,p_2} + \dots + w_{p_n ,t} + h_s − h_t
\]</div>那么对于新图上 $s\to t$ 的长度为 $w$ 的最短路真实的长度为 $w − h_s + h_t$。而原图上任意一边 $x\to y$ 满足 $h_y \le h_x + w_{x,y}$，所以 $w_{x,y} + h_x − h_y \ge 0$。
<details>
<summary>P5905</summary>
<pre><code class="language-cpp">// Problem: P5905 【模板】全源最短路（Johnson）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5905
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
author: Nimbunny
powered by c++14
*/

#include <bits/stdc++.h>
#define int long long
#define pi pair<int, int>

using namespace std;
const int N = 3e5 + 5;
int n, m, h, dis;
vector<pi> e;

inline int read() {
int x;
cin >> x;
return x;
}

signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
n = read(), m = read();
for (int i = 1; i <= m; i++) {
 int u = read(), v = read(), w = read();
 e.push_back(make_pair(v, w));
}
for (int i = 1; i <= n; i++) {
 bool found = false;
 for (int j = 1; j <= n; j++)
 for (auto it : e)
 if (h + it.second < h)
 found = 1, h = h + it.second;
 if (i == n && found) puts("-1"), exit(0);
}
priority_queue<pi, vector<pi>, greater<pi>> q;
for (int i = 1; i <= n; i++) {
 int ans = 0;
 for (int j = 1; j <= n; j++)
 dis = (i == j ? 0 : 1e9);
 q.push(make_pair(0, i));
 while (q.size()) {
 auto t = q.top();
 q.pop();
 int id = t.second;
 if (t.first != dis) continue;
 for (auto v : e) {
 int it = v.first, d = t.first + h - h + v.second;
 if (d < dis) q.push({dis = d, it});
 }
 }
 for (int j = 1; j <= n; j++)
 ans += j * (dis + (dis < 1e9 ? h - h : 0));
 cout << ans << endl;
}
return 0;
}
</code></pre>
</details>
<h2 id="p3403-跳楼机">P3403 跳楼机</h2>
<details>
<summary>题目描述</summary>
给定 $x,y,z,h$，对于 $k\in$，有多少个 $k$ 满足 $\exists ax + by + cz = k, 0 \le a, b, c$。 
$1 \le x, y, z \le 10^5, 1 \le h < 2^{63}$。
</details>
钦定 $x < y < z$，令 $d_i$ 为只通过 $+y, +z$ 能到达的满足 $\bmod x = i$ 的最低楼层，考虑同余最短路，建图：
<ul>
<li>$i\xrightarrow{y}(i+y)\bmod x$</li>
<li>$i\xrightarrow{z}(i+z)\bmod x$</li>
</ul>
跑最短路即可，然后不停地走 $+x$，所以答案为：$\sum \lfloor \frac{h-d_i-1}x \rfloor+1$
<h2 id="cf986f-oppa-funcan-style-remastered">CF986F Oppa Funcan Style Remastered</h2>
<details>
<summary>题目描述</summary>
给定 $n(1\le n\le10^8),k(1\le k\le10^{15})$，问能否将 $n$ 分为若干个 $k$ 的因数（$1$ 除外）之和，每个因数可以用多次。 
共 $t(1\le t\le10^4)$ 组询问，最多有 $50$ 种不同的 $k$。
</details>
改为质因数显然等价。当 $\le 2$ 个质因数时是平凡的，特判和 exgcd 即可。$>2$ 个时最小的质因数 $\le 10^5$，和 P3403 类似，建立同余最短路模型。
<details>
<summary>CF986F</summary>
<pre><code class="language-cpp">
</code></pre>
</details>
<h2 id="cf1163f-indecisive-taxi-fee">*CF1163F Indecisive Taxi Fee</h2>
<details>
<summary>题目描述</summary>
给定一个 $n$ 点 $m$ 边的五向图，有边权。共 $q$ 次询问，每次询问修改第 $i$ 条边权位 $t$，求 $1\to n$ 的最短路，修改不保留。 
$n,m,q\le2\times10^5$。
</details>
我们发现，怎样转化取决于修改的是否是 $1\to n$ 的最短路上的边，所以有以下分讨：
<ul>
<li>如果过修改的不是最短路上的边 $x\to y$，答案为 $\min(dis_{i,n},dis_{1,x}+t+dis_{y,n})$。</li>
<li>如果修改的是最短路上的边，若边权变小则答案为 $\min(dis_{1,n},dis_{1,x}+t+dis_{y,n})$，若变大则是删掉这条边后 $1\to n$ 的最短路与 $dis_{1,x}+t+dis_{y,n}$取 $\min$。</li>
</ul>
易知有以下结论：
<ul>
<li>结论 $1$：$1\to x$ 的最短路必定存在一条与 $1\to n$ 共享且仅共享一条前缀。 
通过最短路树易证。</li>
<li>结论 $2$：删掉第 $i$ 条边后的最短路和 $1\to n$ 的最短路共享一个前缀和后缀。 
由于是无向图，$1\to n$ 的最短路也是 $n\to 1$ 的最短路，根据结论 $1$ 易证。</li>
<li>结论 $3$：中间这段腾空的弧里，有且只有一条非最短路树边。 
根据最短路树易证，不会删了一条换两条进来。</li>
</ul>
所以枚举非最短路边 $x\to y$，从 $x,y$ 分别走若干条树边到达 $1\to n$ 最短路上的两个点 $l,r$，贡献区间为 ，贡献值为 $dis(1, x) + w_{x,y} + dis(y, n)$。 
线段树、或者离线差分 multiset 即可。
<details>
<summary>CF1163F</summary>
<pre><code class="language-cpp">
</code></pre>
</details>
<h2 id="p2483-模板k-短路--sdoi2010-魔法猪学院">P2483 【模板】k 短路 / 魔法猪学院</h2>
<details>
<summary>题目描述</summary>
求长度 $\le E$ 的最短路个数。 
$1\le n\le5000,1\le m\le2\times10^5$。
</details>
建立以 $t$ 为根的最短路树 $T$。
<ul>
<li>性质 $1$： 
令 $P'=P-(P\bigcap T),P$ 为 $s\to t$ 的边集。 
对于 $P'$ 中相邻的两条边 $e,f$（$s$ 到 $t$ 顺序），满足 $f$ 的起点为 $e$ 的终点在 $T$ 上的祖先或自己。</li>
<li>性质 $2$：<div class="math display">\[length_p=dis_{s,t}+\displaystyle\sum_{e\in p',e(u\to v)}{dis_v}+w-dis_u
\]</div></li>
</ul>
令 $\displaystyle\sum_{e\in p',e(u\to v)}{dis_v}+w-dis_u+w-dis_u$ 为 $\Delta p'$ 
问题转化为 $\Delta$ 第 $k$ 小的 $P'$。
用小根堆维护 $P'$，每次取出最小的，当前 $P'$ 的 $P(s\to t)$：
<ul>
<li>替换 $t$ 为起点的边为一条最小的大于它的非最短路边。</li>
<li>加入一条以 $t$ 为起点的最小的非最短路边 $t\to x$，$x$ 在 $T$ 上是 $t$ 的祖先， $t$ 变为 $x$。</li>
</ul>
显然可以按照大小得到所有的 $P'$。使用可持久化合并堆维护祖先除去的所有非最短路边的最下边即可。
<details>
<summary>P2483</summary>
<pre><code class="language-cpp">
/*
author: Nimbunny
powered by c++14
*/

#include <bits/stdc++.h>
#define endl '\n'
#define pi pair<int, int>

using namespace std;
const double eps = 1e-8;
const int N = 5e3 + 10, M = 2e5 + 10, D = 4e6 + 10;
double res, z, dis;
int n, m, x, y, tot, cnt, ans, rt, ch;
bool vis;
pair<double, pi> eg;
vector<int> add;
vector<pair<pi, double>> v;
priority_queue<pair<double, pi>> q;

inline int read() {
int x;
cin >> x;
return x;
}

void dfs(int x) {
vis = true;
int len = v.size();
for (int i = 0; i < len; i++) {
 int y = v.first.first;
 double z = v.second;
 if (vis) continue;
 if (fabs(dis - dis - z) <= eps) {
 v.first.second = 1;
 dfs(y);
 }
}
return;
}

int modify(int rt, int l, int r, int v) {
int p = ++tot;
if (l == r) return p;
int mid = l + r >> 1;
if (v <= mid) {
 ch = modify(ch, l, mid, v);
 ch = ch;
} else {
 ch = modify(ch, mid + 1, r, v);
 ch = ch;
}
return p;
}

int queryfir(int rt, int l, int r) {
if (l == r) return (rt ? l : 0);
int mid = l + r >> 1;
if (ch)
 return queryfir(ch, l, mid);
else
 return queryfir(ch, mid + 1, r);
}

int querynx(int rt, int l, int r, int v) {
if (l == r) return (rt ? (l > v ? l : 0) : 0);
int mid = l + r >> 1;
if (mid <= v)
 return querynx(ch, mid + 1, r, v);
else {
 int tmp = querynx(ch, l, mid, v);
 if (tmp) return tmp;
 return querynx(ch, mid + 1, r, v);
}
}

void dfs2(int x) {
int len = add.size();
for (int i = 0; i < len; i++) rt = modify(rt, 1, cnt, add);
len = v.size();
for (int i = 0; i < len; i++) {
 int y = v.first.first;
 if (v.first.second) {
 rt = rt;
 dfs2(y);
 }
}
return;
}

signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> res;
for (int i = 1; i <= m; i++) {
 cin >> x >> y >> z;
 if (x ^ n) v.push_back({{x, 0}, z});
}
for (int i = 1; i <= n - 1; i++) dis = 1e12;
q.push({0, {n, 0}});
while (q.size()) {
 auto a = q.top();
 q.pop();
 int nw = a.second.first;
 if (vis) continue;
 vis = true;
 for (int i = 0; i < v.size(); i++) {
 int y = v.first.first;
 double z = v.second;
 if (dis > dis + z) {
 dis = dis + z;
 q.push({-dis, {y, 0}});
 }
 }
}
memset(vis, false, sizeof vis);
dfs(n);
for (int i = 1; i <= n; i++)
 for (int j = 0; j < v.size(); j++) {
 int y = v.first.first;
 double z = v.second;
 if (!v.first.second) eg[++cnt] = {dis + z - dis, {y, i}};
 }
sort(eg + 1, eg + cnt + 1);
for (int i = 1; i <= cnt; i++) add.second.first].push_back(i);
dfs2(n);
res -= dis, ans = 1;
int tmp = queryfir(rt, 1, cnt);
if (tmp) q.push({-eg.first, {1, tmp}});
while (q.size()) {
 auto a = q.top();
 q.pop();
 double val = dis - a.first;
 if (res - val <= -eps) break;
 res -= val;
 ans++;
 int c = a.second.first, d = a.second.second;
 int nx = querynx(rt, 1, cnt, d), tmp = eg.second.second;
 if (nx) q.push({a.first + eg.first - eg.first, {c, nx}});
 nx = queryfir(rt, 1, cnt);
 if (nx) q.push({a.first - eg.first, {tmp, nx}});
}
cout << ans << endl;
return 0;
}
</code></pre>
</details> 
来源：https://www.cnblogs.com/Cloudybunny/p/-/Graph_connection_optimization

頁: [1]

琼殿技术论坛's Archiver

各种优化建图、最短路建模技巧