小蓝学习了最短路径之后特别高兴,他定义了一个特别的图,希望找到图中的最短路径。 小蓝的图由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之间的最短路径长度是多少,是指结点1和结点2021这两个结点的最短路径长度么,那根据题目条件差的绝对值为2020没有结点。如果问的是结点1到结点2021之间所有结点之间的的最短路径之和,那可以写两个循环最外层的i从1开始到2021结束,内层的j从1开始到最外层的i+21结束,要考虑去重问题可以设置一个类保存两个结点,重复的跳过不重复的保留,最后再把所有留下来的类的长度相加就可以了