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

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

This article is participating Nuggets team number on-line 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 20212021 points, labelled from11 to20212021 , usegraph[i][j]graph[i][j] means pointii pointjj the side of , there are:

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

among them infinf means the edge weight is infinite, that is, there is no edge connected,lcmlcm represents the least common multiple,absabs represents the absolute value.

Now ask you from the point 11 point20212021What 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)lcm(a, b) = a * b/gcd(a, b) , wheregcdgcd 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 DijkstraDijkstra is solved by the algorithm. The core idea of the algorithm is greedy, usingdist[i]dist[i] means point11 pointiiThe shortest path of , the initial timedist[i]={0,i=1inf,elsedist[i] =/begin{cases} 0,/quad i = 1\inf,/quad else/end{cases}, After each step, the unmarked points are selected distdist minimum pointxx , markxx , reusemin(dist[y],dist[x]+graph[x][y])min(dist[y], dist[x] + graph[x][y]) updatexx gets all successorsyy until all points are marked.

The correctness of this can be understood as follows: The first step must be from distdist is00 points11 departure, then update from point11 Only the shortest path from one edge to other points, and then we find the smallest one from other pointsdist[x]dist[x] , assumingyy represents any point among other points, then there isdist[y] dist[x]dist[y]/geq dist[x] , there will definitely bedist[y]+graph[y][x] dist[x]dist[y] + graph[y][x]/geq dist[x] . This means that there is no suchyy , making the11 toyy againxx cost ratiodist[x]dist[x] is smaller, sodist[x]dist[x] must be11 toxxThe shortest path of . apart fromxx other pointsx x' Not necessarily satisfieddist[x ] dist[y],yA{Other unmarked points}dist[x']/leq dist[y],/quad y/in/{other unmarked points\} , i.e.dist[x ]dist[x']Not necessarily11 tox x' the shortest path, so it can be updated. This also shows that if there are negative side weights,DijkstraDijkstra 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.