2021年12屆藍橋杯C++B組省賽

路徑 自己的寫法

#include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <iostream>using namespace std;const int N = 2200; int g[N][N]; int dist[N]; // 從源點到各點的距離 int book[N]; // 標記是否找到最短的 int n = 2021; int inf = 0x3f3f3f3f;int gcd(int a, int b) {return b ? gcd(b, a % b) : a; }int lcm(int a, int b) {return a * b / gcd(a,b); }void dijkstra(int s, int d) {for (int i = 1; i <= n; i ++ ){dist[i] = g[s][i];}dist[s] = 0;book[s] = 1;int minn;int u = 0, v;for (int i = 2; i <= n; i ++ ){minn = inf;// 尋找所有沒有找到最短路徑的點for (int j = 1; j <= n; j ++ ){if(!book[j] && minn > dist[j]){minn = dist[j];u = j; // 記錄下這個點}}book[u] = 1; // 通過u點 松弛for (v = 1; v <= n; v ++ ){if (g[u][v] < inf && !book[v]){if(dist[v] > dist[u] + g[u][v]){dist[v] = dist[u] + g[u][v];}}}}cout << dist[d] << endl; } int main() {for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= n; j ++ ){if (i != j){if (fabs(i - j) <= 21){g[i][j] = lcm(i, j);g[j][i] = lcm(i, j);}else{g[i][j] = inf;g[j][i] = inf;}}}}dijkstra(1, 2021);return 0; }

總結

以上是生活随笔為你收集整理的2021年12届蓝桥杯C++B组省赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。