直接看题吧，思路有了，但是有些题代码没打。兔子正在加油中。

优化建图

I.（线段树）CF786B Legacy

题目描述

三种连边操作，执行 $q(1\le n\le10^5)$ 次：

$x\xrightarrow{w}y$
$x\xrightarrow{w}y,y\in[l,r]$
$x\xrightarrow{w}y,x\in[l,r]$

求 $s$ 到其余点的最短路。

暴力连边肯定不行。
有没有什么东西是把一个区间拆分成 $\log$ 个的？

当然是线段树优化建图啦。因为加入的是一个区间，所以用线段树上的 $\log$ 个结点来表示区间，对这些结点连边。
对于 $[l,r] \to v$，把 $\log$ 个结点连向线段树上的 $v$，之后把线段树本身连成一颗内向树。
对于 $[l,r] \gets v$，在对线段树内部连边时，显然不能和上一种情况连同一些结点，不然最短路都是 $0$。于是重新开一颗线段树，把这个颗树连成外向树。对于这颗线段树上的 $\log$ 个结点，连向上内向树上的 $v$。
这两颗树上的叶子在原图上是同一个点，所以这两颗树的叶子要连权值为 $0$ 的边（显然只需要外向树向内向树连边）。
对于建出来的图跑最短路，有 $n$ 个结点 $m\log n$ 条边，堆优化 Dijkstra 时间复杂度 $\mathcal{O}(m\log_2 n)$。

CF786B

#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[N], d[N];
bool vis[N];
priority_queue<pi> q;

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

void add(int u,int v,int l){
	g[++cnt] = {v, pre[u], l};
	pre[u] = 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[l] = 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[s] = 0;
    q.push(make_pair(0, s));
    while(q.size()){
        int x = q.top().second;
		q.pop();
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = pre[x]; i; i = g[i].next){
            int to = g[i].to, l = g[i].l;
            if(d[to] > d[x] + l) {
				d[to] = d[x] + l;
				q.push(make_pair(-d[to], 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[i], a[i] + K, 0);
		add(a[i] + K, a[i], 0);
	}
    for(int i = 1; i <= m; i++){
    	op = read();
        if(op==1){
			int x = read(), y = read(), z = read();
			add(a[x] + K, a[y], z);
		}else{
            int x = read(), l = read(), r = read(), w = read();
            tree.modify(1, 1, n, l, r, a[x], w);
        }
    }
    dijkstra(a[s] + K);
    for(int i = 1;i <= n; i++){
    	if(d[a[i]] == 0x3f3f3f3f3f3f3f3f) cout << -1 << " ";
    	else cout << d[a[i]] << " ";
	}
    return 0;
}

II. （后缀树）P5284 [十二省联考 2019] 字符串问题

用后缀树优化建图，然后跑 DAG 上 DP。

P5284


/*+ Nimbunny +*/

#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[N], val[N << 2], laz[N << 2];
void up(int x) {
    val[x] = min(val[x << 1], val[x << 1 | 1]);
}
void down(int x) {
    if (laz[x]) {
        val[x << 1] -= laz[x], val[x << 1 | 1] -= laz[x];
        laz[x << 1] += laz[x], laz[x << 1 | 1] += laz[x];
    }
    laz[x] = 0;
}
void build(int l, int r, int x) {
    laz[x] = val[x] = 0;
    if (l == r) return val[x] = deg[l], 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[x]--, laz[x]++, 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[x] = inf, l;
    int m = l + r >> 1, ans;
    down(x);
    if (!val[x << 1])
        ans = query(l, m, x << 1);
    else
        ans = query(m + 1, r, x << 1 | 1);
    return up(x), ans;
}

// SegTree_Max
ll ini[N << 2], val2[N << 2], laz2[N << 2];
void cmax(ll &x, ll y) {
    x = max(x, y);
}
void up2(int x) {
    val2[x] = max(val2[x << 1], val2[x << 1 | 1]);
}
void down2(int x) {
    if (laz[x] != -1) {
        cmax(laz2[x << 1], laz2[x]), cmax(laz2[x << 1 | 1], laz2[x]);
        cmax(val2[x << 1], laz2[x]), cmax(val2[x << 1 | 1], laz2[x]);
    }
    laz2[x] = -1;
}
void build2(int l, int r, int x) {
    val2[x] = laz2[x] = -1;
    if (l == r) return val2[x] = ini[l], 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[x], v), cmax(laz2[x], 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[x];
    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[N], len[N], ed[N], son[N][S], ff[N][S];
vint FAIL[N];
void ins(char s) {
    int p = las, cur = ++cnt, it = s - 'a';
    len[cur] = len[las] + 1, ed[len[cur]] = cur, las = cur;
    while (p && !son[p][it]) son[p][it] = cur, p = fa[p];
    if (!p) return fa[cur] = 1, void();
    int q = son[p][it];
    if (len[p] + 1 == len[q]) return fa[cur] = q, void();
    int cl = ++cnt;
    fa[cl] = fa[q], fa[q] = fa[cur] = cl, len[cl] = len[p] + 1;
    mcpy(son[cl], son[q]);
    while (son[p][it] == q) son[p][it] = cl, p = fa[p];
}
void build(char *s) {
    for (int i = 1; i <= n; i++) ins(s[i]);
    for (int i = 2; i <= cnt; i++)
        FAIL[fa[i]].pb(i), ff[i][0] = fa[i];
    K = log2(cnt);
    for (int i = 1; i <= K; i++)
        for (int j = 1; j <= cnt; j++)
            ff[j][i] = ff[ff[j][i - 1]][i - 1];
}
int getpos(int l, int r) {
    int p = ed[r];
    for (int i = K; ~i; i--)
        if (r - len[ff[p][i]] + 1 <= l) p = ff[p][i];
    return p;
}

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

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

void clear() {
    // clear SAM
    for (int i = 1; i <= cnt; i++)
        mem(son[i], 0), mem(ff[i], 0), ed[i] = len[i] = fa[i] = 0;
    // clear Fail tree
    for (int i = 1; i <= cnt; i++) FAIL[i].clear(), tag[i].clear();
    for (int i = 1; i <= tot + 1; i++)
        lens[i] = id[i] = sz[i] = deg[i] = 0;
    // clear DAG
    for (int i = 1; i <= na; i++) DAG[i].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[i] = r - l + 1;
        tag[getpos(l, r)].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[i + na] = r - l + 1;
        tag[getpos(l, r)].pb(i + na);
    }
    m = read();
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        DAG[x].pb(y + na);
    }
    dfs(1);
    for (int i = 1; i <= tot; i++) tmp[id[i]] = lens[i];
    for (int i = 1; i <= tot; i++) lens[i] = tmp[i], rev[id[i]] = i;
}

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

III.（倍增 or ST表 + 虚点）P5344 【XR-1】逛森林

解法 $1$：

区间向区间连边，转化为区间向虚点连边，虚点向区间连边。

倍增优化建图，与线段树类似，只不过放到了树上。需要建出两个倍增树，一个管理出边，一个管理入边。时间复杂度为 $\mathcal{O}(m\log n\log(m\log n))$。

解法 $2$：
可以将树通过 dfs 序拍到序列上，并使用 ST 表维护连边。具体地，可以将 $[l,r]$ 拆成 $[l,l+2^k)$ 和 $(r-2^k,r]$，其中 $k$ 为 $\lfloor\log_2(r-l+1)\rfloor$，因为重复连边不影响最终的答案。时间复杂度 $\mathcal{O}(m\log m)$。

P5344

// 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)

/*+ Nimbunny +*/

#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[N];

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

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[u] = v, u != v;
}

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

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

int vis[N], dep[N], fa[N][K], in[N][K], out[N][K];

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

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

int dis[T];
priority_queue<pi, vector<pi>, greater<pi> > q;
void dijkstra(int s) {
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0, q.push({0, s});
    while (!q.empty()) {
        pi t = q.top();
        q.pop();
        int id = t.se, ds = t.fi;
        if (dis[id] < ds) continue;
        for (pi it : e[id])
            if (dis[it.fi] > ds + it.se)
                q.push({dis[it.fi] = 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] = 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[u].pb({v, w}), e[v].pb({u, w});
        }
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs(i, 0, 1);
    for (int i = 1; i <= n; i++)
        e[i].pb({i + n, 0}), e[i + n].pb({i, 0});
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= n; j++)
            in[j][i] = ++node, e[node].pb({in[j][i - 1], 0}),
            e[node].pb({in[fa[j][i - 1]][i - 1], 0}),
            out[j][i] = ++node, e[out[j][i - 1]].pb({node, 0}),
            e[out[fa[j][i - 1]][i - 1]].pb({node, 0}),
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
    for (int i = 1; i <= cnt; i++)
        con(p[i].u1, p[i].v1, ++node, p[i].w, 1),
            con(p[i].u2, p[i].v2, node, 0, 0);
    dijkstra(s);
    for (int i = 1; i <= n; i++)
        cout << (dis[i] < 1e8 ? dis[i] : -1) << " ";
    return 0;
}

IV.（线段树 + 虚点）P1983 [NOIP 2013 普及组] 车站分级

解法 $1$（暴力）：
对于一条线路 $t_1\to t_2\to\dots\to t_s$，将所有编号在该线路之间却没有经过的站点 $p(\in[t_1,t_s]$ 且 $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)$。

P1983

// Problem: P1983 [NOIP 2013 普及组] 车站分级
// 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)

/*+ Nimbunny +*/

#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[N], deg[N << 1], f[N << 1];
bool buc[N << 1];
vector<int> e[N << 1];

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[i], buc[t[i]] = true;
        if (t[s] - t[1] + 1 == s) continue;
        node++;
        for (int i = t[1]; i <= t[s]; i++)
            if (buc[i])
                e[node].push_back(i), deg[i]++;
            else
                e[i].push_back(node), deg[node]++;
    }
    queue<int> q;
    for (int i = 1; i <= node; i++)
        if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (int v : e[t]) {
            f[v] = max(f[v], f[t] + 1);
            if (!--deg[v]) q.push(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= node; i++) ans = max(ans, f[i]);
    cout << ans / 2 + 1 << endl;
    return 0;
}

解法 $3$（线段树 + 虚点）：
点与区间的连边用线段树优化即可。最后跑拓扑也在线段树上跑。时间复杂度 $\mathcal{O}(m\log n)$。

最短路建模

P9351 迷宫 / Maze

题目描述给一个 $r\times c$ 的网格图，有一些障碍物`#`。每次操作可以打通一个 $n\times n$ 的正方形，求将输入的起点和终点四联通的最小操作步数。$1\le n\le r\le c,r\times c\le6\times10^6$。

考虑把打通的代价和变化表示出来，那么就是选择打通就要 $1$ 的代价，然后可以走 $n\times n$ 的 $0$ 权边。但是给每个点新建一个 $n\times n$ 的 $0$ 权图复杂度太大，能不能只建立一个辅助图，同时在这个图上限制只能走 $n\times n$。
如果将一个正方形打通，则可以再上面不管障碍物地乱走，然后在某个地方走出去。所以有三种情况：不管障碍物、管障碍物、随便走不管障碍物。
所以考虑建立两个图，第一个图是原图，上面的 . 都可以走。第二个图描述 $n\times n$ 的覆盖，八联通，边权都为 $1$，限制一次走的边权小于 $n$。然后第一个图的点可以四联通的走到第二个图上，代价为$1$。那么相当于双关键字最短路，两张图也没必要真的建出来，第二个关键字跑满再走第一个关键字，这样就能01bfs了。

P9351

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

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

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[id(i, j)] = (s[j - 1] == '#');
    }
    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[id(x, y)]) continue;
        vis[id(x, y)] = true;
        if (x == tx && y == ty) 
            return cout << t << endl, 0;
        if (h) {
            for (int d = 0; d <= 7; d++) {
                int xx = x + dx8[d];
                int yy = y + dy8[d];
                if (check(xx, yy) && !vis[id(xx, yy)])
                    q.push_back({xx, yy, t, h-1});
            }
        } else {
            for (int d = 0; d <= 3; d++) {
                int xx = x + dx4[d];
                int yy = y + dy4[d];
                if (check(xx, yy) && !vis[id(xx, yy)]) {
                    if (a[id(xx, yy)])
                        q.push_back({xx, yy, t + 1, k - 1});
                    else
                        q.push_front({xx, yy, t, 0});
                }
            }
        }
	}
	return 0;
}

ARC084B

题目描述给定一个整数 $K$，求一个 $K$ 的正整数倍 $S$，使得 $S$ 的数位累加和最小。$2\le K\le105$。

直接做倍数之类的不太好做。注意到 $K$ 很小，可以考虑 $\mod K = 0$ 就是 $K$ 的倍数，从 $\mod K$下手。

考虑从 $1$ 开始，通过 $\times 10$ 和 $+1$ 同时不进位凑一个 $K$ 的倍数，这一定可以做到。
$\times 10$ 对数位和的贡献为 $0,+1$ 的贡献为 $1$，判断是否为倍数只需要考虑 $\mod K$ 是否为 $0$。
建立一个图（不需要真的建）：
- $x\xrightarrow{0} x\times10\mod K$
- $x\xrightarrow{1} (x+1) \mod K$
跑01bfs求出最短路即为答案。

ARC084B


/*+ Nimbunny +*/

#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[N];
bool vis[N];
vector<pi> g[N];
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[i].push_back({(i + 1) % k, 1});
        g[i].push_back({(i * 10) % k, 0});
    }
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 1;
    q.push_back(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop_front();
        if (vis[x]) continue;
        vis[x] = true;
        for (pi i : g[x]) {
            int y = i.first, w = i.second;
            if (dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                if (!w)
                    q.push_front(y);
                else
                    q.push_back(y);
            }
        }
    }
    cout << dis[0] << endl;
    return 0;
}

P7297 [USACO21JAN] Telephone G

题目描述

$n$ 头奶牛，一共 $K$ 种，第 $i$ 头奶牛品种是 $b_i$。给定一个 $K\times K$ 的矩阵 $S$，如果 $S_{i,j}=1$ 表示第 $i$ 种奶牛和第 $j$ 种之间可以交流，第 $i$ 头奶牛和第 $j$ 头之间需要 $\mid i−j\mid$ 的时间交流。求 $1\to n$ 交流的需要的时间。$1\le n\le5\times10^4,1\le K\le50$。

需要刻画哪些奶牛能交流。先把绝对值拆开，然后真的需要每个奶牛都连边吗？
直接建图是 $\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 即可。

P7297

#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[55];
int d[N],rad[55][55];
int v[55][N],tot[55];
int n,k,a[N];
bool vis[N];
priority_queue<pi>q;

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

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

signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	n=read(),k=read();
	for(int i=1;i<=n;i++)
		v[a[i]=read()][++tot[a[i]]]=i;
	for(int i=1;i<=k;i++){
		cin>>s+1;
		for(int j=1;j<=k;j++)
			if(s[j]=='1')
				rad[i][j]=1;
	}
	dijkstra();
	if(d[n]==0x3f3f3f3f)
		return cout<<-1<<endl,0;
	cout<<d[n]<<endl;
	return 0;
}

P4366 [Code+#4] 最短路

题目描述

共 $n$ 个点，$i\xrightarrow{(i\oplus j)\times C}j$，另有 $m$ 条有向边，求 $a\to b$ 的最短路。

异或的每一位是独立的，可以拆开？
考虑把异或边权拆开，$i$ 向 $i \oplus 2^j$ 连边权 $2^j\times C$ 的边（$i\oplus 2^j\le n$）。
然后直接对这 $n\log n+m$ 条边跑最短路即可。

P4366

AT_abc164_E Two Currencies

题目描述

有 $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$ 到其他城市的最少时间。

发现 $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}$ 之间连边，也就是跑分层图最短路，也是非常巧的。

AT_abc164_E

#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[N][M];
vector<AC> g[N][M];

void dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	priority_queue<pii, vector<pii>, greater<pii> > q;
	q.push({0, {1, min(2500ll, s)}});
	dist[1][min(2500ll, s)] = 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[u][x]) continue;
		for(AC a : g[u][x]) {
			if(dist[a.v][a.x] > dist[u][x] + a.b) {
				dist[a.v][a.x] = dist[u][x] + a.b;
				q.push({dist[a.v][a.x], {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[u][i].push_back({v, i - a, b});
			g[v][i].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[u][i].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[u][i]);
		cout << res << endl;
	}
	return 0;
}

*P9370 [APIO2023] 赛博乐园 / cyberland

好题！建议看一下题目。

给定一张 $n$ 个点 $m$ 条边的无向图，经过第 $i$ 条边会用 $w_i$ 的时间。
有些点在经过时可以选择改变总通过时间，多次经过可以多次改变，但是除以 $2$ 只能使用 $k$ 次。

$arr_i = 0$，经过这个点会使得总通过时间为 $0$。
$arr_i = 1$，不改变总通过时间。
$arr_i = 2$，经过这个点会使得总通过时间为 $\frac{\text{总时间}}{2}$。

保证 $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$ 的部分分。

首先把图反着跑，这样总通行时间除以 $2$ 就变成了后续时间都除以 $2$，当前总通过时间为 $0$ 就变成了后续时间都为 $0$。
$K$ 很小，考虑用分层图来做，然后把一个点拆开成 $K+2$ 个，第 $i$ 个代表经过 $i$ 次除以二操作的点，最后一个代表经过清零操作的点，然后跑最短路。注意一下 $H$ 不能多次经过和不能达到为 $−1$，这样就有 $97$ 分了。

仔细想了一下，发现和 P4145 这题一样的思路可以说一样。P4145 是给一个区间开方，显然用线段树，但是一个小于 $10^9$ 的数开 $5$ 次方就已经是 $1$ 了，没有必要再开方了。而这道题，除以二的操作做 $\log_2{\frac{10^5\times 10^9}{10^{-6}}}\approx70$ 次就会变成可忽略值，所以 $K$ 和 $70$ 取最小的那一个就行。

P9370

// Problem: P9370 [APIO2023] 赛博乐园 / 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)

/*+ Nimbunny +*/

#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[N],cnt;
struct node {
    int next, to;
    double w, val;
} g[N];

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[N];
double f[N];

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

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

inline void init(int n,int k){
    for (int i = 0; i <= (n + 1) * (k + 1); i++)
        vis[i] = false, pre[i] = 0, f[i] = 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[i] != H) add(x[i] + j * n, y[i] + j * n, c[i], 1.0);
            if (y[i] != H) add(y[i] + j * n, x[i] + j * n, c[i], 1.0);
            if (a[x[i]] == 2 && y[i] != H && j != k)
                add(y[i] + j * N, x[i] + (j + 1) * N, c[i], 2.0);
            if (a[y[i]] == 2 && x[i] != H && j != k)
                add(x[i] + j * N, y[i] + (j + 1) * N, c[i], 2.0);
        }
    }
    dfs(0);
    if (!vis[H]) return -1;
    priority_queue<ss> q;
    q.push({0, 0});
    f[0] = 0;
    for (int i = 0; i < n; i++)
        if (a[i] == 0 && vis[i])
        	q.push({i, 0}), f[i] = 0;
    // dijkstra
    for (int i = 0; i <= N + 1; i++) vis[i] = false;
    while (!q.empty()) {
        int t = q.top().now;
        q.pop();
        if (vis[t]) continue;
        vis[t] = true;
        for (int i = pre[t]; i; i = g[i].next) {
            if (f[g[i].to] > (f[t] + g[i].w) / g[i].val) {
                f[g[i].to] = (f[t] + g[i].w) / g[i].val;
                if (!vis[g[i].to])
                    q.push({g[i].to, f[g[i].to]});
            }
        }
    }
    double ans = 1e24;
    for (int i = 0; i <= k; i++) ans = min(ans, f[H + i * n]);
    return ans;
}

P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus

题目描述

给定一个 $n(2\le n\le200)$ 个点 $m(1\le m\le5\times10^4)$ 条边的有向图，可以选择或者不选一条边翻转方向，求 $1 \to n$ 的最短路加 $n \to 1$ 的最短路的和。

求出最短路树，枚举翻转那条边。
如果翻转的是树边，重新跑最短路，树边只有 $\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$ 翻转后的更短的路径。

P6880

P9724 [EC Final 2022] Chase Game

题目描述

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$ 处受到最后一次攻击。

如果瞬移了一次，那么以后的伤害都是 $d,d − 1,\dots,1,d$，顺移到的都是之前走过的位置，如果距离没变，那么距离终点的最短路也没变，白吃了伤害。
剩下的就是最开始距离小于 $d$ 的位置，对这些位置跑最短路。之后直接走到终点的最短路，此时已经瞬移了一次了。

P9724

#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[N], dn[N], ans = LLONG_MAX, dis[N];
vector<int> G[N];
bool vis[N];

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[x] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v : G[u]){
            if(!vis[v]){
                vis[v] = 1;
                q.push(v);
                dis[v] = dis[u] + 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[x] = 0;
    q.push({0, x});
    while(!q.empty()){
        int u = q.top().yy;
        q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int v : G[u]){
            if(dk[v] >= d)ans = min(ans, dis[u] + gs(dn[v] + 1));
            else if(dis[u] + d - dk[v] < dis[v]){
                dis[v] = dis[u] + d - dk[v];
                q.push({dis[v], 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[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(k, dk), bfs(n, dn), dij(1);
    cout << min(ans, dis[n]);
    return 0;
}

P5905 【模板】全源最短路（Johnson）

题目描述

又一种全员最短路，但是有负权。

我们考虑使用 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$ 的最短路

\[(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 \]

那么对于新图上 $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$。

P5905

// 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)

/*+ Nimbunny +*/

#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[N], dis[N];
vector<pi> e[N];

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[u].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[j])
                if (h[j] + it.second < h[it.first])
                    found = 1, h[it.first] = h[j] + 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[j] = (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[id]) continue;
            for (auto v : e[id]) {
                int it = v.first, d = t.first + h[id] - h[it] + v.second;
                if (d < dis[it]) q.push({dis[it] = d, it});
            }
        }
        for (int j = 1; j <= n; j++)
            ans += j * (dis[j] + (dis[j] < 1e9 ? h[j] - h[i] : 0));
        cout << ans << endl;
    }
    return 0;
}

P3403 跳楼机

题目描述

给定 $x,y,z,h$，对于 $k\in[0,h−1]$，有多少个 $k$ 满足 $\exists ax + by + cz = k, 0 \le a, b, c$。
$1 \le x, y, z \le 10^5, 1 \le h < 2^{63}$。

钦定 $x < y < z$，令 $d_i$ 为只通过 $+y, +z$ 能到达的满足 $\bmod x = i$ 的最低楼层，考虑同余最短路，建图：

$i\xrightarrow{y}(i+y)\bmod x$
$i\xrightarrow{z}(i+z)\bmod x$

跑最短路即可，然后不停地走 $+x$，所以答案为：$\sum \lfloor \frac{h-d_i-1}x \rfloor+1$

CF986F Oppa Funcan Style Remastered

题目描述

给定 $n(1\le n\le10^8),k(1\le k\le10^{15})$，问能否将 $n$ 分为若干个 $k$ 的因数（$1$ 除外）之和，每个因数可以用多次。
共 $t(1\le t\le10^4)$ 组询问，最多有 $50$ 种不同的 $k$。

改为质因数显然等价。当 $\le 2$ 个质因数时是平凡的，特判和 exgcd 即可。$>2$ 个时最小的质因数 $\le 10^5$，和 P3403 类似，建立同余最短路模型。

CF986F

*CF1163F Indecisive Taxi Fee

题目描述

给定一个 $n$ 点 $m$ 边的五向图，有边权。共 $q$ 次询问，每次询问修改第 $i$ 条边权位 $t$，求 $1\to n$ 的最短路，修改不保留。
$n,m,q\le2\times10^5$。

我们发现，怎样转化取决于修改的是否是 $1\to n$ 的最短路上的边，所以有以下分讨：

如果过修改的不是最短路上的边 $x\to y$，答案为 $\min(dis_{i,n},dis_{1,x}+t+dis_{y,n})$。
如果修改的是最短路上的边，若边权变小则答案为 $\min(dis_{1,n},dis_{1,x}+t+dis_{y,n})$，若变大则是删掉这条边后 $1\to n$ 的最短路与 $dis_{1,x}+t+dis_{y,n}$取 $\min$。

易知有以下结论：

结论 $1$：$1\to x$ 的最短路必定存在一条与 $1\to n$ 共享且仅共享一条前缀。
通过最短路树易证。
结论 $2$：删掉第 $i$ 条边后的最短路和 $1\to n$ 的最短路共享一个前缀和后缀。
由于是无向图，$1\to n$ 的最短路也是 $n\to 1$ 的最短路，根据结论 $1$ 易证。
结论 $3$：中间这段腾空的弧里，有且只有一条非最短路树边。
根据最短路树易证，不会删了一条换两条进来。

所以枚举非最短路边 $x\to y$，从 $x,y$ 分别走若干条树边到达 $1\to n$ 最短路上的两个点 $l,r$，贡献区间为 $[l,r]$，贡献值为 $dis(1, x) + w_{x,y} + dis(y, n)$。
线段树、或者离线差分 multiset 即可。

CF1163F

P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院

题目描述

求长度 $\le E$ 的最短路个数。
$1\le n\le5000,1\le m\le2\times10^5$。

建立以 $t$ 为根的最短路树 $T$。

性质 $1$：
令 $P’=P-(P\bigcap T),P$ 为 $s\to t$ 的边集。
对于 $P’$ 中相邻的两条边 $e,f$（$s$ 到 $t$ 顺序），满足 $f$ 的起点为 $e$ 的终点在 $T$ 上的祖先或自己。
性质 $2$：

\[length_p=dis_{s,t}+\displaystyle\sum_{e\in p’,e(u\to v)}{dis_v}+w-dis_u \]