题目描述
blablabla
样例
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3000;
ll mp[N][N]; /// 注意开ll数组,,由INF0x7fffffffffffffff
const ll INF = 2e18;
/// @brief Floyd算法 求单元源最短路径 n^3复杂度
/// @param n
void Floyd(int n){
for(int k = 1; k <= n; ++ k)
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j){
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
}
}
int gcd(int i, int j){
return j? gcd(j, i%j) : i;
}
int main(){
int n = 2021;
//建图
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= n; ++ j){
if(i == j)
mp[i][j] = 0; //结点相同时
else if(abs(j-i)<=21)
mp[i][j] = mp[j][i] = i*j/gcd(i,j); //符合条件时
else
mp[i][j] = mp[j][i] = INF; //不符合条件时,取无限^_^
}
}
Floyd(n);
cout << mp[1][2021]; //求从结点1到结点2021的最短路径
system("pause");
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla