【路径——Dijkstra】

题目

代码

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 2025, M = N * N;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
int n = 2021;
void add(int a, int b, int c)
{
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, 1}), dist[1] = 0;

    while (pq.size())
    {
        auto u = pq.top();
        pq.pop();
        if (dist[u.y] < u.x)
            continue;

        for (int i = h[u.y]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[u.y] + w[i])
            {
                dist[j] = dist[u.y] + w[i];
                pq.push({dist[j], j});
            }
        }
    }

    return dist[2021];
}
int main()
{
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j && abs(i - j) <= 21)
                add(i, j, i * j / __gcd(i, j));
        }
    }

    cout << dijkstra();
}