44 lines
1.2 KiB
C++
44 lines
1.2 KiB
C++
// lanqiao 1460 路径(Dijkstra)
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 3e3 + 10, INF = INT_MAX;
|
||
int g[N][N]; // 领接矩阵
|
||
bool vis[N]; // 标记数组
|
||
int mindis[N]; // 最短路数组
|
||
int s = 1, n = 2021;
|
||
|
||
// 朴素版dijkstra-时间复杂度 O(n^2)
|
||
void dijkstra(int s){
|
||
mindis[s] = 0; // 自己到自己的距离为0
|
||
for(int i = 1; i <= n; i++){
|
||
int mi = INF, cur = 0;
|
||
for(int j = 1; j <= n; j++){
|
||
if(!vis[j] && mindis[j] < mi){
|
||
mi = mindis[j];
|
||
cur = j;
|
||
}
|
||
}
|
||
vis[cur] = 1; // 已经确定起点到cur点的最短距离，所以要标记
|
||
// 以cur点作为中转点去更新起点到其他各点的距离
|
||
for(int i = 1; i <= n; i++){
|
||
if(!vis[i]&&g[cur][i] != 0){
|
||
mindis[i] = min(mindis[i], mi + g[cur][i]);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
int main(){
|
||
for(int i = 1; i <= n; i++){
|
||
for(int j = max(i-21, 1); j <= min(i+21, 2021); j++){
|
||
if(i != j) g[i][j] = g[j][i] = lcm(i, j);
|
||
}
|
||
}
|
||
fill(mindis, mindis + N, INF);
|
||
dijkstra(s);
|
||
cout << mindis[n] << endl;
|
||
return 0;
|
||
}
|
||
|
||
// correct output 10266837
|