思路：用迪杰斯特拉算法跑一遍，這題的意義在于重溫圖論里邊的一些算法和最小公約數(shù)(gcd)最大公倍數(shù)的求法(lcm)

這里圖采用鏈?zhǔn)角跋蛐谴鎯?#xff0c;可以參考這篇博客：

鏈?zhǔn)角跋蛐?#xff08;詳解）_菜雞的博客-CSDN博客_鏈?zhǔn)角跋蛐?/p>

而關(guān)于迪杰斯特拉算法，可以參考一下這篇博客：

迪杰斯特拉（Dijkstra)算法最通俗易懂的講解_goodxin_ie的博客-CSDN博客_迪杰斯特拉算法

我的理解就是維護(hù)一個(gè)距離數(shù)組和一個(gè)集合s，每次從在s外的點(diǎn)中選出從到s最短的一個(gè)點(diǎn)，加入集合，然后更新其他未在集合中的鄰接點(diǎn)的最小路徑值

代碼如下所示：

#include <iostream> #include <queue> #include <memory.h> using namespace std; typedef long long ll;const int Max = 1e6 + 5; int u[Max], v[Max], w[Max]; int g = 0, first[Max], nex[Max]; struct node {int n, w;bool operator<(const node& a)const{return w > a.w;}node(int a, int b){n = a;w = b;} }; ll dis[Max], b[Max]; priority_queue<node> que; //鏈?zhǔn)角跋蛐谴鎯?void add(int a, int b, int c) {u[++g] = a;v[g] = b;w[g] = c;nex[g] = first[a];//記錄上一條以a為起點(diǎn)的邊在uvw中的存儲位置first[a] = g;//以a為起點(diǎn)的最后輸入的邊的存儲位置 }ll gcd(ll a, ll b) {if (a == 0) return b;return gcd(b % a, a); }ll lcm(ll a, ll b) {return a * b / gcd(a, b); }int main() {// 請?jiān)诖溯斎肽拇amemset(first, -1, sizeof(first));memset(dis, 0x7f, sizeof(dis));for (int i = 1; i <= 2021; ++i){for (int j = i + 1; j - i <= 21 && j <= 2021; ++j){add(i, j, lcm(i, j));add(j, i, lcm(i, j));}}que.push(node(1, 0));dis[1] = 0;while (!que.empty()){node no = que.top();que.pop();if (b[no.n]) continue;//已經(jīng)加入集合dis[no.n] = no.w;b[no.n] = 1;//加入集合//對這個(gè)節(jié)點(diǎn)的所有不在集合中的鄰接點(diǎn) 更新最小值for (int i = first[no.n]; i != -1; i = nex[i]){if (b[v[i]]) continue;if (dis[u[i]] + w[i] < dis[v[i]]){dis[v[i]] = dis[u[i]] + w[i];que.push(node(v[i], dis[u[i]] + w[i]));}}}cout << dis[2021];return 0; }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯真题：路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。