This article is participating Nuggets team number online activity, click to see giant spring recruit jobs
1. Title description:
The question I m going to write today is the E question path of the 12th Blue Bridge Cup C/C++ B group freshly released today. Many people on the Internet say that this year s question is a lot more difficult, but most of the questions are still examined Classic simple algorithm, such as this question.
The main idea of the topic: a total of $2021$ points, labelled from$1$ to$2021$ , use$graph[i][j]$ means point$i$ point$j$ the side of$j$ , there are:
among them $inf$ means the edge weight is infinite, that is, there is no edge connected,$lcm$ represents the least common multiple,$abs$ represents the absolute value.
Now ask you from the point $1$ point$2021$What is the shortest path length of$2$$0$$2$$1$ ?
2. Thinking analysis:
The solution to this problem is very simple. To put it bluntly, there are two steps: 1. Build a picture, 2. Find the shortest path.

Building a graph:
Because the data range of this question is very small, we can directly use the adjacency matrix to represent the graph, and we need to know a mathematical knowledge when calculating edge weights:$lcm(a, b) = a * b/gcd(a, b)$ , where$gcd$ represents the greatest common divisor. 
Finding the shortest path: Finding the shortest path is a very basic problem in graph theory, and there are many ways to solve it, because this question is just a fillintheblank question, so choose the simplest one directly $Dijkstra$ is solved by the algorithm. The core idea of the algorithm is greedy, using$dist[i]$ means point$1$ point$i$The shortest path of$i$ , the initial time$dist[i] =/begin{cases} 0,/quad i = 1\inf,/quad else/end{cases}$, After each step, the unmarked points are selected $dist$ minimum point$x$ , mark$x$ , reuse$min(dist[y], dist[x] + graph[x][y])$ update$x$ gets all successors$y$ until all points are marked.
The correctness of this can be understood as follows: The first step must be from $dist$ is$0$ points$1$ departure, then update from point$1$ Only the shortest path from one edge to other points, and then we find the smallest one from other points$dist[x]$ , assuming$y$ represents any point among other points, then there is$dist[y]/geq dist[x]$ , there will definitely be$dist[y] + graph[y][x]/geq dist[x]$ . This means that there is no such$y$ , making the$1$ to$y$ again$x$ cost ratio$dist[x]$ is smaller, so$dist[x]$ must be$1$ to$x$The shortest path of$x$ . apart from$x$ other points$x'$ Not necessarily satisfied$dist[x']/leq dist[y],/quad y/in/{other unmarked points\}$ , i.e.$dist[x']$Not necessarily$1$ to$x'$ the shortest path, so it can be updated. This also shows that if there are negative side weights,$Dijkstra$ algorithm is not applicable, but that is no longer within the scope of this question.
3. AC code:
/*
* The path to question E of the 12th Lanqiao Cup C/C++ Group B
*/
# include <iostream>
# include <cstring>
using namespace std;
using ll = long long ;
const int maxn = 2077 ;
const int inf = 0x3f3f3f3f ;
int graph[maxn][maxn], dist[maxn];
bool mark[maxn];
const int n = 2021 ;
int gcd ( int a, int b) {
return b == 0 ? a: gcd (b, a% b);
}
int lcm ( int a, int b) {
return a * b/ gcd (a, b);
}
void buildGraph () {
memset (graph, 0x3f , sizeof (graph));
for ( int i = 1 ; i <= n; ++i) {
for ( int j = max ( 1 , i 21 ); j < = min (n, i + 21 ); ++j) {
graph[i][j] = graph[j][i] = lcm (i, j);
}
}
for ( int i = 1 ; i <= n; ++i) {
graph[i][i] = 0 ;
}
}
void dijkstra () {
memset (dist, 0x3f , sizeof (dist));
dist[ 1 ] = 0 ;
//Because every time we infer the shortest path of at least another point based on the known shortest point.
//We knew dist[1] = 0 from the beginning, so we only need to update n 1 time
for ( int i = 1 ; i <n; ++i) {
int x = 0 ;
for ( int j = 1 ; j <= n; ++j) {
if (!mark[j] && (x == 0  dist[j] <dist[x])) {
x = j;
}
}
//Remember to mark
mark[x] = true ;
for ( int y = 1 ; y <= n; ++y) {
dist[y] = min (dist[y], dist[x] + graph[x][y]);
}
}
}
int main () {
buildGraph ();
dijkstra ();
cout << dist[n] << endl;
}
Copy code
4. Summary:
By the way, the answer is: 10266837. The students who participated in this morning's competition can correct the answers.