博客

题目

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点
之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条
长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无
向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题。

结果

10266837

代码

import java.util.Scanner;
import java.util.Vector;

public class Main {
	static int min= Integer.MAX_VALUE;
	static int sum= 0;
	static int n;
	static int m;
	static int[][] g;
	static int[] dist;
	static Vector<Integer> visit;
	static Vector<Integer> left;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n=2021;
		m=21;
		g=new int[n+1][n+1];
		dist=new int[n+1];
		visit=new Vector<>();
		left=new Vector<>();
		for (int i = 1; i <= n; i++) {
			left.add(i);
			dist[i]=Integer.MAX_VALUE;
			for (int j = i; j <= n; j++) {
				if(i==j){
					g[i][j]=0;
				}else if(Math.abs(i-j)<=m) {
					int r=gcd(i,j);
					g[i][j]=(i/r)*j;
					g[j][i]=(i/r)*j;
				}else {
					g[i][j]=Integer.MAX_VALUE;
					g[j][i]=Integer.MAX_VALUE;
				}
			}
		}
		dijkstra(1);
		System.out.println(dist[2021]);
	}
	private static void dijkstra(int k) {
		for (int i = 0; i < dist.length; i++) {
			dist[i]=g[k][i];
		}
		left.remove((Object)k);
		int index=0;
		while(left.size()!=0) {
			min=Integer.MAX_VALUE;
			for (int i = 1; i < dist.length; i++) {
				if(dist[i]<min && left.contains((Object)i)) {
					min=dist[i];
					index=i;
				}
			}
			left.remove((Object)index);
			for (int j = 1; j < dist.length; j++) {
				if(g[index][j]!=Integer.MAX_VALUE) {
					dist[j]=Math.min(dist[j], dist[index]+g[index][j]);
				}
			}
		}
		
	}
	private static int gcd(int i, int j) {
		return j==0?i:gcd(j, i%j);
	}
	
}