某桥杯的一道小孩儿题

发布于 2021-12-01  522 次阅读


先看题目

方法,通过gcd去找到权重列表

然后floyd去跑距离

#include<iostream>
#include<math.h>
using namespace std;
int map[2021][2021];
int gcd(int a, int b){
    int temp;
    while(b)
    {    
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
int main(){

    for (int i=1;i<=2021;i++){
        for (int j=1;j<=2021;j++){
            if(abs(i-j)<=21){
                int weight=i*j/gcd(i,j);
                map[i-1][j-1]=weight;
                map[j-1][i-1]=weight;
            }else{
                map[j-1][i-1]=0x3f3f3f3f;
                map[i-1][j-1]=0x3f3f3f3f;
            }
        }
    }
    for (int i=0;i<2021;i++){
        for (int j=0;j<2021;j++){
            for (int k=0;k<2021;k++){
                if(map[j][k]>map[j][i]+map[i][k]){
                    map[j][k]=map[j][i]+map[i][k];
                }
            }
        }
    }
    cout<<map[0][2020];
}

不会写珂朵莉树的废柴ACMer