『最短路·裴蜀定理』CF510D Fox And Jumping

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

给出 $n$ 张卡片，分别有 $l_i$ 和 $c_i$。

在一条无限长的纸带上，你可以选择花 $c_i$ 的钱来购买卡片 $i$，从此以后可以向左或向右跳 $l_i$ 个单位。

问你至少花多少元钱才能够跳到纸带上全部位置。若不行，输出 $?1$。

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

若对于数字 $a$ 和数字 $b$ ，根据裴蜀定理，方程$ax+by=c(\mathrm{g}\mathrm{c}\mathrm{d}(a,b)|c)$恒有解。

因此若我们能拼出 $x$ 的任何倍数，我们就可以用 $c_i$ 拼出 $\gcd (x,l_i)$ 任何数。

这对应了一个最短路模型，我们以 $0$ 跑最短路即可，主要要用map或哈希存储。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <bits/stdc++.h>
#define int long longusing namespace std;
const int N = 2e5;int n;
int c[N], l[N];
map < int, int > vis, dis;
priority_queue < pair<int, int> > q;int read(void)
{
    int s = 0, w = 0; char c = getchar();while (!isdigit(c)) w |= c == '-', c = getchar();while (isdigit(c)) s = s*10+c-48, c = getchar();return w ? -s : s;
}int gcd(int a, int b) {
    if (b == 0) return a;return gcd(b, a % b);
}int Dijkstra(void)
{
    q.push({
    dis[0] = 0LL, 0LL});while (q.size()){
    int x = q.top().second; q.pop();if (vis[x]) continue; vis[x] = 1;if (x == 1) return dis[1];for (int i=1;i<=n;++i){
    int y = gcd(l[i], x);if (dis.count(y) == 0) dis[y] = 1e18;if (dis[x] + c[i] < dis[y]) {
     dis[y] = dis[x] + c[i];q.push({
    -dis[y], y});} }}return -1;
}signed main(void)
{
    n = read();for (int i=1;i<=n;++i) l[i] = read();for (int i=1;i<=n;++i) c[i] = read();cout << Dijkstra() << endl;return 0;
}