题目

代码

#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();
}