蓝桥杯 路径

#include <bits/stdc++.h>
using namespace std;
vector<int> dp(2021+1,INT_MAX);
int main()
{
  dp[1]=0;
    for(int cur=2;cur<=2021;cur++)
    {
      int pre=max(cur-21,1);
      for(;pre<cur;pre++)
      {
        if(dp[pre]<INT_MAX)
        {
          dp[cur]=min(dp[cur],dp[pre]+(pre*cur/__gcd(pre,cur)));
        }
      }
    }
    cout<<dp[2021];
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g(2044, vector<int>(2044, 1e9));
int main()
{
    int n = 2021;
    for (int i = 1; i <= n; i++)
    {
        g[i][i] = 0;
        for (int j = i + 1; j <= i + 21; j++)
        {
            g[i][j] = g[j][i] = i * j / __gcd(i, j);
        }
    }
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (g[i][k] + g[k][j] < g[i][j])
                {
                    g[i][j] = g[i][k] + g[k][j];
                }
            }
        }
    }
    cout << g[1][2021];
    return 0;
}