第十二届蓝桥杯 试题 E: 路径 题解

题目

答案

10266837

方法一：Dijkstra

解析

最短路模板题。构建邻接矩阵，套Dijkstra模板

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 0x3f3f3f3f
#define N 2025
int edges[N][N];
int d[N];
bool vis[N];

int gcd(int a, int b){return b==0? a : gcd(b, a%b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
int main(){
    memset(edges, INF, sizeof(edges));//edges数组所有元素初始化为INF
    //邻接矩阵
	for(int i = 1;i<N;i++){
        edges[i][i] = 0;
        for(int j = i+1;j < N;j++){
            int w = lcm(i, j);
            edges[i][j] = edges[j][i] = w;
        }
    }
    memset(d, INF, sizeof(d));  //d数组所有元素初始化为INF
    memset(vis, false, sizeof(vis));    //vis数组所有元素初始化为false
    d[1] = 0;
    //Dijkstra
    for(int i = 1;i<N;i++){
        int x = 0;  //找到下一个未确定的最短路径的点
        for(int j = 1;j<N;j++) if(!vis[j] && d[j] < d[x]) x= j;
        vis[x] =1;//标记为已确定
        for(int j = max(1, x-21); j<=min(N, x +21);j++){    //用该点更新连通的点
            d[j] = min(d[j] , d[x] + edges[x][j]);
        }
    }
    cout<< d[2021] <<endl;
    return 0;
}

重写了一遍代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2022;
int dist[N];
bool st[N];

int main() {
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    dist[1] = 0;
    
    for (int i = 1; i < N; i ++) {
        int t = -1;
        for (int j = 1; j < N; j ++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
                
        st[t] = true;
        for (int j = max(t - 21, 1); j <= min(t + 21, N - 1); j ++)
            dist[j] = min(dist[j], dist[t] + t / __gcd(t, j) * j);
    }
    
    cout << dist[2021] << endl;
}

方法二：动态规划

解析：

由于边的特殊性（边权为两数的最小公倍数，且两数的绝对值相差不超过21才连通），那么其实从1到某点的最短路径必然是递增的，证明：略（不会）

代码：

#include <bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f
#define N 2025
int d[N];

int gcd(int a, int b){return b==0? a : gcd(b, a%b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
int main(){    
    memset(d, INF, sizeof(d));
    d[1]  =0;
	for(int i = 1;i<N;i++){
        for(int j = i+1;j < N && j-i <= 21;j++){
            d[j] = min(d[j], lcm(i, j)+d[i]);
        }
    }
    cout<< d[2021] <<endl;
    return 0;
}

最后

以上就是落寞台灯为你收集整理的第十二届蓝桥杯 试题 E: 路径 题解的全部内容，希望文章能够帮你解决第十二届蓝桥杯 试题 E: 路径 题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。