【蓝桥杯学习记录】路径
一、题目
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
二、解题思路
题目中说到了最短路径，肯定要用最短路径，由于只需要求的1-2021之间的最短路径就可以了，所以可以用Dijkstra算法（下称D算法）。D算法的思路是将所有顶点分为两个顶点集，一个叫生长点集，另一个叫非生长点集，开始生长点集只有第一个，即起始点，然后根据起始点算出起始点到其他每个点的距离，然后找到最短的路径之后记录这个点的坐标k，循环整个距离数组，判断之前的距离dist[i]是否大于dist[k]+length（k，i）(即从起始点直接到i的距离是否大于从起始经过k点到i)如果大于就dist[i]=dist[k]+length（k，i），最后将这个点加入到生长点集中同时将dist[k]置0。循环直到所有的点都加入到了生长点集。
最后当选到了2021时计算完最短距离之后输出。
本题还需要用到最小公倍数，最小公倍数可以用x*y*gcd(x,y)得到，但是由于本题只有两点下标相差小于等于21才有距离，所以可以判断以下两点是否相差小于等于21，否则距离为MAX（即没有路径）
三、完整代码
