【藍橋杯學習記錄】路徑
一、題目
小藍的圖由 2021 個結(jié)點組成，依次編號 1 至 2021。
對于兩個不同的結(jié)點 a, b，如果 a 和 b 的差的絕對值大于 21，則兩個結(jié)點 之間沒有邊相連；如果 a 和 b 的差的絕對值小于等于 21，則兩個點之間有一條 長度為 a 和 b 的最小公倍數(shù)的無向邊相連。
例如：結(jié)點 1 和結(jié)點 23 之間沒有邊相連；結(jié)點 3 和結(jié)點 24 之間有一條無 向邊，長度為 24；結(jié)點 15 和結(jié)點 25 之間有一條無向邊，長度為 75。
請計算，結(jié)點 1 和結(jié)點 2021 之間的最短路徑長度是多少。
二、解題思路
題目中說到了最短路徑，肯定要用最短路徑，由于只需要求的1-2021之間的最短路徑就可以了，所以可以用Dijkstra算法（下稱D算法）。D算法的思路是將所有頂點分為兩個頂點集，一個叫生長點集，另一個叫非生長點集，開始生長點集只有第一個，即起始點，然后根據(jù)起始點算出起始點到其他每個點的距離，然后找到最短的路徑之后記錄這個點的坐標k，循環(huán)整個距離數(shù)組，判斷之前的距離dist[i]是否大于dist[k]+length（k，i）(即從起始點直接到i的距離是否大于從起始經(jīng)過k點到i)如果大于就dist[i]=dist[k]+length（k，i），最后將這個點加入到生長點集中同時將dist[k]置0。循環(huán)直到所有的點都加入到了生長點集。
最后當選到了2021時計算完最短距離之后輸出。
本題還需要用到最小公倍數(shù)，最小公倍數(shù)可以用x*y*gcd(x,y)得到，但是由于本題只有兩點下標相差小于等于21才有距離，所以可以判斷以下兩點是否相差小于等于21，否則距離為MAX（即沒有路徑）
三、完整代碼
