【JAVA】无向连通图到达所有点必须经过固定点成本之和的最小值（Pro20210903）（Dijkstra + DP）

• • 题目
  • 思路
  • 代码

题目

略

思路

每次到达下一个点必须经过1号店，可以拆解为从当前点到1号点的最短路径，加上从1号点到目的地的最短路径。
也就是说，整个过程可以分解为：
1号点到剩余所有点：在下面会包含，不用单独列举（计算）
2号点到剩余所有点：【2 --> 1 --> 3 --> 1 --> 4 --> 1 --> 5… --> N-1 --> 1 --> N】
3号点到剩余所有点：--------------【3 --> 1 --> 4 --> 1 --> 5… --> N-1 --> 1 --> N】
4号点到剩余所有点：----------------------------【4 --> 1 --> 5… --> N-1 --> 1 --> N】
…
N-1号点到剩余所有点：--------------------------------------------------【N-1 --> 1 --> N】

可以观察出：
过程中均为1号点和其它点的路程
且：
【1 --> 2】或【2 --> 1】最短路径使用次数：1
【1 --> 3】或【3 --> 1】最短路径使用次数：2
…
【1 --> N-1】或【N-1 --> 1】最短路径使用次数：N - 2
【N --> 3】或【N --> 1】最短路径使用次数：N - 1

则：

1. 使用Dijkstra，求出1号点到所有点的最短路径COST（无向图，也就是所有点到1号点的最短路径）；
2. 遍历1号点到所有点的最短路径，对于i点，ASW += (i - 1) * COST[i]；
3. ASW即为所求。

代码

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int T, N, M;
	static ArrayList<Edg>[] DATA; // 原始数据
	static long COST[], ASW;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("D:\\SW\\TestCase\\sample_input_20210813.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			COST = new long[N + 1];
			ASW = 0L;

			DATA = new ArrayList[N + 1];
			for (int i = 1; i <= N; i++)
				DATA[i] = new ArrayList<>();

			// 邻接链表读入边、权值数据并存储
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());

				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				long cost = Long.parseLong(st.nextToken());

				DATA[from].add(new Edg(to, cost));
				DATA[to].add(new Edg(from, cost));
			}

			// 迪杰斯特拉求最短路径
			dijkstra();

			for (int i = 2; i <= N; i++)
				ASW += (i - 1) * COST[i];

			System.out.printf("#%d %d\n", tc, ASW);
		}
	}

	static void dijkstra() {
		boolean visited[] = new boolean[N + 1]; // 已求得最短路径的点标记为true
		int visitedCount = 0; // 已求得最短路径的点个数

		// 按当前到达点的成本升序排序
		PriorityQueue<Edg> pq = new PriorityQueue<>(new Comparator<Edg>() {
			@Override
			public int compare(Edg o1, Edg o2) {
				return Long.compare(o1.cost, o2.cost);
			}
		});
		pq.add(new Edg(1, 0L)); // 设定起点为1号点

		while (!pq.isEmpty()) {
			Edg now = pq.poll(); // 获取当前到达的点

			if (visited[now.point]) // 当前点的最短路径已求得
				continue;

			// 更新当前点的最短路径，并标记
			visited[now.point] = true;
			COST[now.point] = now.cost;

			if (++visitedCount == N) // 所有点的最短路径已求得
				break;

			// 遍历当前点的连接点
			for (Edg next : DATA[now.point]) {
				if (visited[next.point]) // 若当前节点的最短路径已经确定
					continue;

				// 则松弛操作
				if (COST[next.point] < now.cost + next.cost) {
					COST[next.point] = now.cost + next.cost;
					visited[now.point] = true;

					pq.add(new Edg(next.point, now.cost + next.cost));
				}
			}
		}
	}

	static class Edg {
		int point;
		long cost;

		public Edg(int p, long cost) {
			this.point = p;
			this.cost = cost;
		}
	}
}