First line is a number N means that the next N lines are the N edges in the graph. Each of the N lines has two value v1 v2 which are the two nodes’ ID linked by this edge. 0 < N < 10000000 After that there is a single line with a number M which means the next M lines are the M special nodes. Each of the M lines has one value v which means the node’s ID. 0 <= M <= N/2
Sum of All nodes' minimum distance
2 1 2 2 3 1 2
2
import java.util.*; public class Main { // 迪杰斯特拉算法-取特殊点不断更新最后求和 public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); // 构建无向图的邻接表-坑点在于不知道结点的范围我们默认取[0,10000000) LinkedList<int[]>[] graph = new LinkedList[10000000]; for (int i = 0; i < 10000000; i++) { graph[i] = new LinkedList<>(); } // 记录一下结点的范围用于计算 int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { int start = in.nextInt(), end = in.nextInt(); max = Math.max(Math.max(max, end), start); min = Math.min(Math.min(min, end), start); graph[start].add(new int[]{end, 1}); graph[end].add(new int[]{start, 1}); } dis = new int[10000000]; Arrays.fill(dis, Integer.MAX_VALUE); // 调用 int m = in.nextInt(); for (int i = 0; i < m; i++) { int special = in.nextInt(); dijkstra(graph, special); } int sum = 0; for (int i = min; i <= max; i++) { // 注意从min开始到max计算即可 if (dis[i] == Integer.MAX_VALUE) sum += -1; else sum += dis[i]; } System.out.println(sum); } static int[] dis; // 迪杰斯特拉eng算就是了 public static void dijkstra(LinkedList<int[]>[] graph, int start) { dis[start] = 0; PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[1]-b[1]); q.offer(new int[]{start, 0}); while (!q.isEmpty()) { int[] node = q.poll(); int id = node[0], d = node[1]; if (dis[id] < d) continue; for (int[] next : graph[id]) { int nid = next[0], nd = next[1]; if (dis[id] + nd < dis[nid]) { dis[nid] = dis[id] + nd; q.offer(new int[]{nid, dis[nid]}); } } } } }