# Twelfth Blue Bridge Cup C/C++ B Group E Question Path: Solution|Check in

## 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 , there are:

$graph[i][j] =/begin{cases} lcm(i, j),/quad abs(i-j)/leq 21\inf,/quad else/end{cases}$

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. 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.

1. 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.

2. 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 fill-in-the-blank 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 , 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 . 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 = 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.