34 lines
948 B
C++
34 lines
948 B
C++
// lanqiao 1460 路径(floyd)
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 3e3 + 10, INF = INT_MAX;
|
|
bool vis[N]; // 标记数组
|
|
int mindis[N][N]; // 最短路数组
|
|
int s = 1, n = 2021;
|
|
|
|
// floyd求多源最短路-时间复杂度-O(n^3)
|
|
void floyd(){
|
|
// 枚举中转点
|
|
for(int k = 1; k <= n; k++){
|
|
// 枚举任意两点
|
|
for(int i = 1; i <= n; i++){
|
|
for(int j = 1; j <= n; j++){
|
|
if(mindis[i][k] != INF && mindis[k][j] != INF){
|
|
mindis[i][j] = min(mindis[i][j], mindis[i][k] + mindis[k][j]);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
int main(){
|
|
fill(mindis[0], mindis[0] + N * N, INF);
|
|
for(int i = 1; i <= n; i++){
|
|
for(int j = max(i-21, 1); j <= min(i+21, 2021); j++){
|
|
if(i != j) mindis[i][j] = mindis[j][i] = lcm(i, j);
|
|
}
|
|
}
|
|
floyd();
|
|
cout << mindis[1][n] << endl;
|
|
return 0;
|
|
}
|
|
// correct output 10266837
|