Bezout 定理例题。

最短路

（出自：《繁凡的算法笔记》）

预处理。首先引入节点 0，同时进行建图。对于每个数都引入一个节点 u，对于数 a_i，令其对应的节点权值为 u.w = a_i。

若 \gcd(u.w, a_j) = v.w，则建立一条有向边 e = u \to v，并令边权 e.w = c_j，表示选择这一个数的代价。则是否可行就转化为节点 0 是否可达 1，最小代价解就是 0 到 1 的最短路。用 Dijkstra 算法求解节点 0 到节点 1 的最短路即可。

如果进一步观察还可以发现，建出来的图是一个有向无环图，所以可以用 DP 直接求最短路径，不必借助 Dijkstra 算法。

DP

原题可以视为一个 0-1 背包（（链接未公开）），要求在 a_1, \dots, a_n 中取部分元素 x_{i_1}, \dots, a_{i_k}，满足 \gcd(a_{i_1}, \dots, a_{i_k}) = 1 且价值 c_{i_1} + \cdots + c_{i_k} 最小。部分最大公因数因为满足偏序关系，可以视为一种特殊的容量。

因此，可以用传统背包问题的思路解决。设 f_{i, j} 表示考虑前 i 个物品且最大公因数为 j 的最小代价，则有转移方程：

如同普通背包问题一样，可以滚动数组优化，减少一维。而这里 300 个数可达的最大公因数 j 是很稀疏的，因此还可以使用 Hash 表代替数组，优化内存并减少枚举量。

因此这里的核心代码如下：

	dp[0] = 0;
	for (size_t i = 1; i <= n; i++)
	{
		auto last_dp = dp;
		for (auto p: last_dp)
		{
			unsigned x = p.first;
			unsigned d = gcd(x, l[i]);
			if (dp.find(d) == dp.end())
			{
				dp[d] = INF;
			}
			dp[d] = min(dp[d], p.second + c[i]);
		}
	}
	if (dp.find(1) == dp.end())
	{
		cout << "-1";
	}
	else
	{
		cout << dp[1];
	}

最短路和 DP 的等价性

事实上，这里最短路和 DP 是等价的。最短路解法建出的有向无环图就是 DP 过程的状态转移图。