具体出处

2021蓝桥杯cpp组

【第十二届】【省赛】【B组】

路径 - 蓝桥云课 (lanqiao.cn)

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

运行限制

• 最大运行时间：1s

• 最大运行内存: 128M

AC代码

答案：10266837

法1：dijkstra模板题

#include
using namespace std;typedef pair PII;const int N = 100005;
int e[N], w[N], ne[N], h[N], idx;
int dist[N];
bool st[N];int gcd(int i, int j){if(j) return gcd(j, i%j);else return i;
}int lcm(int i, int j){return i*j/gcd(i, j);
}void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void dijk(int s){memset(dist, 127, sizeof dist);priority_queue, greater > heap;dist[s] = 0;heap.push({0, s});while(heap.size()){PII t = heap.top();heap.pop();int ver = t.second, distance = t.first;if(st[ver]) continue;st[ver] = 1;for(int i = h[ver]; i!=-1; i = ne[i]){int j = e[i];if(dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.push({dist[j], j});}}}
}int main(){memset(h, -1, sizeof h);for(int i = 1; i<=2020; i++){for(int j = i+1; j<=i+21 && j<=2021; ++j){add(i, j, lcm(i,j));add(j, i, lcm(i,j));}}dijk(1);//源点编号为s cout<

法2：floyd模板题（跑的比较慢）

#include
using namespace std;const int n = 2021;
int f[2025][2025];int gcd(int a, int b){if(b) return gcd(b, a%b);else return a;
}int lcm(int a, int b){return a*b/gcd(a,b);
}int main(){memset(f, 63, sizeof f);for(int i = 1; i<=2020; ++i)for(int j = i+1; j<=2021 && j<=i+21; ++j)f[i][j] = lcm(i, j);//floydfor(int k = 1; k<=n; ++k)for(int i = 1; i<=n; ++i)for(int j = 1; j<=n; ++j)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);cout<

法3：动态规划dp最短路（代码量偏小，思维量偏大）

#include
using namespace std;
int dp[2025];  //dp[j]:1到j的最短路径长度（min） int gcd(int a, int b){if(b) return gcd(b, a%b);else return a;
}int lcm(int a, int b){return a*b/gcd(a,b);
}int main(){for(int i = 1; i<2021; ++i)for(int j = i+1; j<=2021 && j<=i+21; ++j){if(dp[j]==0) dp[j] = dp[i] + lcm(i,j);else dp[j] = min(dp[j], dp[i] + lcm(i,j));}cout<