[C++知识库]路径（gcdgbs）

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

#include <stdio.h>
#include <stdlib.h>
int gcd(int a,int b){ //最大公约数
    if(a%b==0)
      return b;
    else
      return gcd(b,a%b);
  }
int gbs(int a,int b){ //最小公倍数
    return a*b/gcd(a,b);
  }
int min(int a,int b){
  return a<b?a:b;
}
int main(int argc, char *argv[])
{
  // 请在此输入您的代码
  int i,j,f[2022]={0};
  for(i=1;i<=2021;i++){
    for(j=i+1;j<=i+21 && j<=2021;j++){
      if(f[j]==0)
        f[j]=f[i]+gbs(i,j);
      else
        f[j]=min(f[j],f[i]+gbs(i,j));
    }
  }
  printf("%d",f[2021]);
  return 0;
}