「学习笔记」同余最短路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pil;
#define fir first
#define sec second

const int N = 1e7 + 5;

int n, m, seed, mod;
int a[N];
ll dis[N];
bool vis[N];

void dijkstra() {
	priority_queue<pil, vector<pil>, greater<pil>> q;
	for (int i = 0; i <= mod; ++ i) {
		dis[i] = 1e18;
	}
	q.push({0, 0});
	dis[0] = 0;
	while (!q.empty()) {
		pil it = q.top();
		q.pop();
		int u = it.second;
		if (dis[u] != it.first)	continue;
		for (int i = 1; i <= n; ++ i) {
			int v = (u + a[i]) % mod;
			if (dis[v] > dis[u] + a[i]) {
				dis[v] = dis[u] + a[i]; // 找到最小的能被拼出的数
				q.push({dis[v], v});
			}
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &seed);
	mt19937 rng(seed);
	auto get = [&]() {
		uniform_int_distribution<int> qwq(2, m);
		return qwq(rng);
	};
	mod = m;
	for (int i = 1; i <= n; i++) {
		a[i] = get();
		mod = min(mod, a[i]);
	}
	dijkstra();
	ll ans = -1;
	for (int i = 0; i < mod; ++ i) {
		ans = max(ans, dis[i] - mod);
		// dis 中存的是最小的能被拼出的数
		//所以只要再 -mod,就是最大的不能拼出的数
	}
	printf("%lld\n", ans);
	return 0;
}