注：本题来自顺丰竞赛（2023年：SF-【未来科技赛道-编程方向】第3题）
解题思路：迪杰斯特拉
1、分析题目
首先分析一波题目，一定要读懂题目！
它仅仅要求从1号城市到第n号城市即可，也就是说不需要全连通！（即不需要使用并查集）
——我们知道，迪杰斯特拉可用于解决：单源点到其他任意点的最短路径！
● 实现步骤
(1) 先使用迪杰斯特拉算法，求出1号点到n号点的最短路径。（当然如果不可达，就无法求出，我们假定不可达的路径长度为-1）
(2) 使用魔法值。
这里用了【贪心】的思想。因为魔法可以从一个城市传送到任意另一个城市，除了起点和终点。那么我们就可以找起点的最近一跳邻居A，找终点的最近一跳邻居B（这里最近是指时间最短，如果A、B有一个找不到，那么说明无法使用魔法值，假定无法使用魔法值返回-1），然后使用魔法从A传送到B，这个总时间就是使用魔法值可以实现的最小时间。
(3) 进行取舍。
如果使用迪杰斯特拉算法，得出1到n的最短路径为-1，且使用魔法值得出的最小时间也为-1，说明无法完成运货，结果返回-1；
如果使用迪杰斯特拉算法，得出1到n的最短路径为-1，但使用魔法值存在有效时间，说明需要使用魔法，结果返回使用魔法值的最小时间；
如果使用迪杰斯特拉算法，得出1到n的最短路径有效，但使用魔法值得出的最小时间为-1，说明不用魔法，直接可以完成运货，返回迪杰斯特拉算法计算的1到n最少时间；
如果迪杰斯特拉酸和和使用魔法值两者计算的最小时间都有效，那么结果返回两者的最小值。
⭐ 迪杰斯特拉回顾
1.1 算法思想
(1) 对于图G=(V,E)，先定义两个集合：
● 第一组S：已经求出的最短路径的点集合（初始时，仅包含源点v0）
● 第二组V-S：还没有求出最短路径的点集合（初始时为V-{v0}）
(2) 通过将第一组S中的点作为中间点，更新第二组V-S中的点到源点v0的最短距离。
⭕ 实际上，点是一个一个加入到S中的，每当加入一个新的顶点v到顶点集S，对第二组剩余的各个顶点而言，多了一个“中转”顶点，从而多了一个“中转”路径，所以要对第二组剩余的各个顶点的最短路径长度进行更新。
⭕ 但我们在实际代码实现的时候，不需将V-S中的所有点更新，而是只更新V-S中v的邻居。
如果点u不是v的邻居，它又在V-S集合中，而且假定u到源点v0的最短距离需要依靠点v，那么它不用被更新吗？我们来分析一下：假设u的最短路径为：v0→……→v→……→k→u。
a) k在V-S中，那么k会在将来被加入S，那个时候会更新u的最短路径长度。那k的最短路径长度什么时候更新？一样的道理……
b) k在S中，如果u到源点v0的最短距离需要依靠点v，说明k的最短路径可能更新，说明k不能比v更先加入S集合，与假定矛盾。所以k只能在V-S中。
(3) 当V-S组的点在当前轮次更新完毕后，从V-S中挑选一个到源点v0最短的点！作为新加入第一组S的点。
● 理解：找到离源点v0最近的点（假定为v，v到v0的最短距离目前为path），此时这个点不可能存在有别的路径比path还短。所以它已经找到了最短路径，应加入第一组S！
重复上述过程n-1次，直到所有的点都从第二组V-S，加入到第一组S。（如果(3)中找不到离v0最近的点，说明此时已经没有点可以再被并入S，可以结束算法。）
1.2 具体实现
(1) 数据结构
● 一维数组S[i]：布尔类型，标识vi是否已经加入第一组S；
● 一维数组Pre[i]：整型类型，标识当前最短路径中最后一跳的前驱节点；
● 一维数组dist[i]：记录从源点v0到vi的当前最短路径长度（初始值：如果v0到vi有边，那么边上的权值作为初始值；如果没有边，则记录为-1表示不可达）**
(2) 代码实现
这里假定源点v0为1；
● 边集可以使用【邻接矩阵】或者【邻接表】。
下面这里，边集用Map<Integer, Map<Integer, Integer>>表示，(1, 3) ∈ E，且权重为10：map.get(1).get(3) = 10 && map.get(3).get(1) = 10（无向图）——但是要注意，如果使用map，【当两个点存在多条边】时，如果不加以判断，可能会出现覆盖现象。
// 已经求得最短距离的点集
boolean[] S = new boolean[n + 1];
// 到1的最短距离，如果没有和1的直接边，则初始化为-1
int[] dist = new int[n + 1];
// 记录当前最短路径的前驱节点
int[] pre = new int[n + 1];
// -------------------初始化-----------------------
for (int i = 1; i <= n; i++) {
if (map.containsKey(1) && map.get(1).containsKey(i)) {
dist[i] = map.get(1).get(i);
pre[i] = 1;
} else{
dist[i] = -1;
pre[i] = -1;
}
}
dist[1] = 0;
pre[1] = -1;
S[1] = true;
// --------------------执行（n-1）轮次------------------------
for (int i = 1; i <= (n - 1); i++) {
// v不在S中
int v = findNodeWithMinEdge(n);
if(v == -1) break; // v找不到
// v加入S集合
S[v] = true;
// 此时,dist[v]就确定不会改变了，即v已经找到离源点最短路径
// 更新和dist[v]相关的边（v作为S集合中新的中间点，更新另一个集合的dist）
// 不需要更新另一个集合的所有点，只需要更新另一个集合中它的一跳邻居（因为另一个集合中其他受影响点，后面会更新）
if(!map.containsKey(v)) continue; // 说明没有需要更新
Set<Integer> neighbours_set = map.get(v);
for (int j : neighbours_set) {
if (!S[j]) {
int tmpDist = map.get(j).get(v) + dist[v];
if (dist[j] == -1 || dist[j] > tmpDist) {
dist[j] = tmpDist;
pre[j] = v;
}
}
}
}
// 找到最小边（指的是到源点最短的边，即这里对应Dist数组），返回对应的点
public int findNodeWithMinEdge(int n) {
long minDist = -1;
int v = -1;
for(int i=1; i<=n; i++){
if(!S[i] && dist[i] != -1 && (minDist == -1 || dist[i] < minDist)){
minDist = dist[i];
v = i;
}
}
return v;
}
2、代码实现
⭕ 竞赛中需要注意的几点：
(1) 测试数据中两个城市之间可能有多条边
(2) 判断离1号城市最近的其他城市（dist数组）时，不能遍历所有点，会超时，需要用到【优先队列】。
——因此这里边集使用邻接表（类型为List<int[]>[]，List数组，数组中的元素表示从下标i出发的边，每条边类型为int[]{u, w}）加入优先队列的元素类型（离源点v0的边）被设置为long[]{u, w}，方便优先队列比较（map不能处理）
(3) 【魔法值结果】、以及【离1号城市的最短时间（dist数组中的值）】可能会超出Integer的范围。
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
// 到达1的边（优先队列），为了快速找到最小边【包含我们新增的不存在的捷径】
private static Queue<long[]> pq = new PriorityQueue<>(new Comparator<long[]>(){
public int compare(long[] a, long b[]){
if(a[1] < b[1]) return -1;
else if(a[1] > b[1]) return 1;
else return 0;
}
});
// 邻接表（要考虑两个城市有多条边的情况）
private static List<int[]>[] adj;
// 对应迪杰斯特拉已经求出（离源点）最短路径的点集
private static boolean[] used;
// 对应迪杰斯特拉的距离数组（离源点的距离）
private static long[] dist;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
String[] line_list = line.split(" ");
int n = Integer.valueOf(line_list[0]);
int m = Integer.valueOf(line_list[1]);
int x = Integer.valueOf(line_list[2]);
List<int[]>[] adjTmp = new List[n+1]; // 定义泛型数组，声明和开辟空间要同时，这样才能类型推断（如果分开，编译时会进行类型擦除）
adj = adjTmp;
for(int i=1; i<=n; i++){
adj[i] = new ArrayList<int[]>();
}
// 构造边
for (int i = 0; i < m; i++) {
line = in.nextLine();
line_list = line.split(" ");
int u = Integer.valueOf(line_list[0]);
int v = Integer.valueOf(line_list[1]);
int k = Integer.valueOf(line_list[2]);
adj[u].add(new int[]{v, k});
adj[v].add(new int[]{u, k});
}
// ----------利用迪杰斯特拉思想---------
// 已经求得最短距离的点集
used = new boolean[n + 1];
// 到1的最短距离，如果没有和1的直接边，则初始化为-1
dist = new long[n + 1];
for(int i=1; i<=n; i++){
dist[i] = -1;
}
dist[1] = 0;
pq.offer(new long[]{1, 0});
// 执行n轮
for (int i = 1; i <= n; i++) {
// v不在used中
// int v = findNodeWithMinEdge(n);
long[] vArr = findNodeWithMinEdgeByPQ();
int v = (int)vArr[0];
long w = vArr[1];
// 加入used集合
if (v == -1) break;
dist[v] = w;
if(v == n) break;
used[v] = true;
// 此时,time[v]就确定不会改变了，即v已经找到离源点最短路径
// 更新和time[v]相关的边（v作为used集合中新的中间点，更新另一个集合的time）
// 不需要更新另一个集合的所有点，只需要更新另一个集合中它的一跳邻居（因为另一个集合中其他受影响点，后面会更新）
for (int[] jArr:adj[v]) {
int j = jArr[0];
if (!used[j]) {
long timeTmp = jArr[1] + dist[v];
// 加入优先队列
pq.offer(new long[]{j, timeTmp});
}
}
}
// --------------如果使用魔法值--------------
long magicTime = useMagic(n, x);
// System.out.println("魔法值" + magicTime);
// System.out.println("迪杰斯特拉" + time[n]);
// -----------------取舍-----------------
if (magicTime == -1 && dist[n] == -1) System.out.println(-1);
else if (dist[n] == -1) System.out.println(magicTime);
else if (magicTime == -1) System.out.println(dist[n]);
else System.out.println(Math.min(dist[n], magicTime));
}
// 从优先队列中拿最小边
public static long[] findNodeWithMinEdgeByPQ(){
while(!pq.isEmpty()){
long[] edge = pq.poll();
if(!used[(int)edge[0]]){
return edge;
}
}
return new long[]{-1, -1};
}
// 使用魔法的时间
public static long useMagic(int n, long magic) {
long minStartTime = Integer.MAX_VALUE;
List<int[]> startEdges = adj[1];
if (startEdges.size() == 0) return -1;
for(int[] e:startEdges){
if(e[1] < minStartTime) minStartTime = e[1];
}
long minEndTime = Integer.MAX_VALUE;
List<int[]> endEdges = adj[n];
if (endEdges.size() == 0) return -1;
for(int[] e:endEdges){
if(e[1] < minEndTime) minEndTime = e[1];
}
return minStartTime + minEndTime + magic;
}
}
