路径

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

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

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

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

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

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

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

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

提交答案

#include <stdio.h>//求1到达2021的最短路径
#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)//最小公倍数=a*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=1,j,f[2022]={0};//f[n]表示1到n的最短路径长
/*先求1能直接到达的点（2..22）更新f数组内的数据，
把已经求出最短路径的点归到一类(i)，再求这类点能直接到达的点(j)最短路径，
多个不同点能到达同一个点，可以通过循环求出f[n]的最佳结果*/
  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));}}
//比较最短路径是比较1到点j的路径长,而不是i到j的路径长！！
  printf("%d",f[2021]);
  return 0;
}