import java.util.*; public class 1806 { static int n; static int[] t = new int[10]; static int[] telegraph = new int[50005]; static int[] dis = new int[50005]; static int[] pre = new int[50005]; static boolean[] vis = new boolean[50005]; static ArrayList<Integer> path = new ArrayList<Integer>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); for (int i = 0; i < 10; i++) { t[i] = sc.nextInt(); } for (int i = 1; i <= n; i++) { telegraph[i] = sc.nextInt(); } dijkstra(1); if (dis[n] == Integer.MAX_VALUE) { System.out.println("-1"); } else { System.out.println(dis[n]); getPath(n); System.out.println(path.size()); for (int i = 0; i < path.size(); i++) { System.out.print(path.get(i) + " "); } } } private static void dijkstra(int s) { Arrays.fill(dis, Integer.MAX_VALUE); dis[s] = 0; for (int i = 1; i <= n; i++) { pre[i] = i; } for (int k = 0; k < n; k++) { int u = -1; int minDis = Integer.MAX_VALUE; for (int i = 1; i <= n; i++) { if (!vis[i] && dis[i] < minDis) { u = i; minDis = dis[i]; } } if (u == -1) { break; } vis[u] = true; for (int i = 1; i <= n; i++) { if (!vis[i]) { int w = getWeight(telegraph[u], telegraph[i]); if (dis[u] + w < dis[i]) { dis[i] = dis[u] + w; pre[i] = u; } } } } } private static int getWeight(int a, int b) { int weight = 0; String s1 = String.valueOf(a); String s2 = String.valueOf(b); int len = Math.min(s1.length(), s2.length()); for (int i = 0; i < len; i++) { if (s1.charAt(i) != s2.charAt(i)) { weight = t[i]; break; } } return weight; } private static void getPath(int u) { if (u != 1) { getPath(pre[u]); } path.add(u); } }解释一下该代码的运行过程
时间: 2024-04-27 15:23:17 浏览: 117
Einleser:java.util.Scanner 的示例
这段代码实现了一个基于Dijkstra算法的最短路径问题求解,输入的数据包括电报码的位数n,每个数字所需的时间t[i],以及n个电报码。程序首先调用dijkstra函数,计算从起点1到终点n的最短路径,同时记录每个节点的前驱节点pre[i]和到起点的距离dis[i]。然后判断是否存在从起点1到终点n的路径,如果不存在则输出-1,否则输出最短路径的长度以及路径上的节点。
其中,dijkstra函数的核心是循环n次,每次选择距离起点最近的未访问节点u,并更新与u相邻且未访问的节点i的距离和前驱节点。getWeight函数用于计算两个电报码之间的距离,即两个数字的码位不同的位置的时长之和。getPath函数用于回溯最短路径的前驱节点,得到完整的路径。最后,程序输出路径时采用了ArrayList存储路径节点,便于遍历输出。
阅读全文