路徑

問(wèn)題描述
小藍(lán)學(xué)習(xí)了最短路徑之后特別高興，他定義了一個(gè)特別的圖，希望找到圖中的最短路徑。

小藍(lán)的圖由 2021 個(gè)結(jié)點(diǎn)組成，依次編號(hào) 1 至 2021。

對(duì)于兩個(gè)不同的結(jié)點(diǎn) a, b，如果 a 和 b 的差的絕對(duì)值大于 21，則兩個(gè)結(jié)點(diǎn)之間沒(méi)有邊相連；如果 a 和 b 的差的絕對(duì)值小于等于 21，則兩個(gè)點(diǎn)之間有一條長(zhǎng)度為 a 和 b 的最小公倍數(shù)的無(wú)向邊相連。

例如：結(jié)點(diǎn) 1 和結(jié)點(diǎn) 23 之間沒(méi)有邊相連；結(jié)點(diǎn) 3 和結(jié)點(diǎn) 24 之間有一條無(wú)向邊，長(zhǎng)度為 24；結(jié)點(diǎn) 15 和結(jié)點(diǎn) 25 之間有一條無(wú)向邊，長(zhǎng)度為 75。

請(qǐng)計(jì)算，結(jié)點(diǎn) 1 和結(jié)點(diǎn) 2021 之間的最短路徑長(zhǎng)度是多少。

完整代碼

public class 路徑 {
	static int[][] a = new int[2022][2022];
	static final int INF = 99999999;
	
	private static void floyd() {
		for (int k = 1; k <= 2021; k++) {
			for (int i = 1; i <= 2021; i++) {
				for (int j = 1; j <= 2021; j++) {
					if (i != j && a[i][j] > a[i][k] + a[k][j]) {
						a[i][j] = a[i][k] + a[k][j];
					}
				}
			}
		}
	}
	
	private static int (int a, int b) {
		return b == 0 ? a : (b, a % b);
	}
	
	public static void main(String[] args) {
		for (int i = 1; i <= 2021; i++) {
			for (int j = 1; j <= 2021; j++) {
				a[i][j] = INF;
			}
		}
		
		for (int i = 1; i <= 2021; i++) {
			int st = Math.max(i - 21, 1);
			for (int j = st; j <= i; j++) {
				int lcm = i * j / (j, i);
				a[i][j] = lcm;
				a[j][i] = lcm;
			}
		}
		
		floyd();
		
		System.out.println(a[1][2021]); // 10266837
	}
	
}