路径—省赛java

十二届蓝桥杯省赛真题E题—路径

蓝桥填空题比较好的地方就是可以直接暴力循环，不用优化算法，不用担心超时

题解：

public class 路径 {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) {//1.记录各个点之间的距离，大于21的为0    int[][] floyd = new int[n][n];//下标代表两个结点，floyd[][]代表两个节点间距离    for(int i = 0;i < n;i++)     for(int j = i+1;j < n;j++)    if(j <= i+21)    floyd[i][j] = floyd[j][i] = lcm(i+1,j+1);    //暴力循环    for(int i = 0;i < n;i++)    for(int j = 0;j < n;j++)    for(int k = 0;k < n;k++)    //把最小长度赋值给floyd[][]    if(floyd[i][j] != 0 && floyd[j][k] != 0 && (floyd[i][k] == 0 || floyd[i][k] > floyd[i][j]+floyd[j][k]))    floyd[i][k] = floyd[i][j] + floyd[j][k];    System.out.println(floyd[0][n-1]);}}