【每日一题】蓝桥杯历年真题题解 -路径

点击蓝字关注我们

今日「每日一题」来啦！历年真题题目：路径。还没有加入专属刷题群的小伙伴，记得扫码哟～（每天会在群里发蓝桥杯历年真题）

题目描述

解题思路

参考代码

1、C/C++ A&B&C组

#include<bits/stdc++.h>typedef long long ll;using namespace std;const int maxn = 3000;const ll INF = 1e18;ll mp[maxn][maxn];void floyd(int n){    for(int k = 1;k <= n;k++){        for(int i = 1;i <= n;i++){            for(int j = 1;j <= n;j++){                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);            }        }    }}int main(){    int n = 2021;    for(int i = 1;i <= n;i++){        for(int j = 1;j <= n;j++){            if(i == j) mp[i][j] = 0;            else if(abs(i - j) <= 21) mp[i][j] = mp[j][i] = i * j / __gcd(i, j);            else mp[i][j] = mp[j][i] = INF;        }    }    floyd(n);    cout << mp[1][2021];    return 0;}

2、Java A&B&C组

public class Main {
    static final int n = 2021;
    static int gcd(int a, int b) {        return b == 0 ? a : gcd(b, a % b);    }
    static int lcm(int a, int b) {        return a * b / gcd(a, b);    }
    public static void main(String[] args) {        int[][] floyd = new int[n][n];        for (int i = 0; i < n; i++)            for (int j = i + 1; j < n && j < i + 22; j++)                floyd[i][j] = floyd[j][i] = lcm(i + 1, j + 1);        for (int k = 0; k < n; k++)            for (int i = 0; i < n; i++)                for (int j = 0; j < n; j++)                    if (floyd[i][k] != 0 && floyd[k][j] != 0 && (floyd[i][j] == 0 || floyd[i][k] + floyd[k][j] < floyd[i][j]))                        floyd[i][j] = floyd[i][k] + floyd[k][j];        System.out.println(floyd[0][n - 1]);    }}

2、Python组

import math
def lcm(a, b):    return int(a * b / math.gcd(a, b))
n = 2021g = [[0 for i in range(1, n + 2)] for j in range(1, n + 2)]for i in range(1, n + 1):    for j in range(1, n + 1):        if i == j:            g[i][j] = g[j][i] = 0        elif abs(i - j) <= 21:            g[i][j] = g[j][i] = lcm(i, j)        else:            g[i][j] = 1000000000for k in range(1, n + 1):    for i in range(1, n + 1):        for j in range(1, n + 1):            if g[i][j] > g[i][k] + g[k][j]:                g[i][j] = g[i][k] + g[k][j]print(g[1][n])