注：本題來自順豐競賽（2023年：SF-【未來科技賽道-編程方向】第3題）
解題思路：迪杰斯特拉
1、分析題目
首先分析一波題目，一定要讀懂題目！
它僅僅要求從1號城市到第n號城市即可，也就是說不需要全連通！（即不需要使用并查集）
——我們知道，迪杰斯特拉可用于解決：單源點到其他任意點的最短路徑！
● 實現(xiàn)步驟
(1) 先使用迪杰斯特拉算法，求出1號點到n號點的最短路徑。（當然如果不可達，就無法求出，我們假定不可達的路徑長度為-1）
(2) 使用魔法值。
?這里用了【貪心】的思想。因為魔法可以從一個城市傳送到任意另一個城市，除了起點和終點。那么我們就可以找起點的最近一跳鄰居A，找終點的最近一跳鄰居B（這里最近是指時間最短，如果A、B有一個找不到，那么說明無法使用魔法值，假定無法使用魔法值返回-1），然后使用魔法從A傳送到B，這個總時間就是使用魔法值可以實現(xiàn)的最小時間。
(3) 進行取舍。
?如果使用迪杰斯特拉算法，得出1到n的最短路徑為-1，且使用魔法值得出的最小時間也為-1，說明無法完成運貨，結(jié)果返回-1；
?如果使用迪杰斯特拉算法，得出1到n的最短路徑為-1，但使用魔法值存在有效時間，說明需要使用魔法，結(jié)果返回使用魔法值的最小時間；
?如果使用迪杰斯特拉算法，得出1到n的最短路徑有效，但使用魔法值得出的最小時間為-1，說明不用魔法，直接可以完成運貨，返回迪杰斯特拉算法計算的1到n最少時間；
?如果迪杰斯特拉酸和和使用魔法值兩者計算的最小時間都有效，那么結(jié)果返回兩者的最小值。
? 迪杰斯特拉回顧
1.1 算法思想
(1) 對于圖G=(V,E)，先定義兩個集合：
● 第一組S：已經(jīng)求出的最短路徑的點集合（初始時，僅包含源點v0）
● 第二組V-S：還沒有求出最短路徑的點集合（初始時為V-{v0}）
(2) 通過將第一組S中的點作為中間點，更新第二組V-S中的點到源點v0的最短距離。
? 實際上，點是一個一個加入到S中的，每當加入一個新的頂點v到頂點集S，對第二組剩余的各個頂點而言，多了一個“中轉(zhuǎn)”頂點，從而多了一個“中轉(zhuǎn)”路徑，所以要對第二組剩余的各個頂點的最短路徑長度進行更新。
? 但我們在實際代碼實現(xiàn)的時候，不需將V-S中的所有點更新，而是只更新V-S中v的鄰居。
如果點u不是v的鄰居，它又在V-S集合中，而且假定u到源點v0的最短距離需要依靠點v，那么它不用被更新嗎？我們來分析一下：假設(shè)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還短。所以它已經(jīng)找到了最短路徑，應加入第一組S！
重復上述過程n-1次，直到所有的點都從第二組V-S，加入到第一組S。（如果(3)中找不到離v0最近的點，說明此時已經(jīng)沒有點可以再被并入S，可以結(jié)束算法。）
1.2 具體實現(xiàn)
(1) 數(shù)據(jù)結(jié)構(gòu)
● 一維數(shù)組S[i]：布爾類型，標識vi是否已經(jīng)加入第一組S；
● 一維數(shù)組Pre[i]：整型類型，標識當前最短路徑中最后一跳的前驅(qū)節(jié)點；
● 一維數(shù)組dist[i]：記錄從源點v0到vi的當前最短路徑長度（初始值：如果v0到vi有邊，那么邊上的權(quán)值作為初始值；如果沒有邊，則記錄為-1表示不可達）**
(2) 代碼實現(xiàn)
這里假定源點v0為1；
● 邊集可以使用【鄰接矩陣】或者【鄰接表】。
下面這里，邊集用Map<Integer, Map<Integer, Integer>>表示，(1, 3) ∈ E，且權(quán)重為10：map.get(1).get(3) = 10 && map.get(3).get(1) = 10（無向圖）——但是要注意，如果使用map，【當兩個點存在多條邊】時，如果不加以判斷，可能會出現(xiàn)覆蓋現(xiàn)象。
// 已經(jīng)求得最短距離的點集
boolean[] S = new boolean[n + 1];
// 到1的最短距離，如果沒有和1的直接邊，則初始化為-1
int[] dist = new int[n + 1];
// 記錄當前最短路徑的前驅(qū)節(jié)點
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;
// --------------------執(zhí)行（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已經(jīng)找到離源點最短路徑
// 更新和dist[v]相關(guān)的邊（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數(shù)組），返回對應的點
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、代碼實現(xiàn)
? 競賽中需要注意的幾點：
(1) 測試數(shù)據(jù)中兩個城市之間可能有多條邊
(2) 判斷離1號城市最近的其他城市（dist數(shù)組）時，不能遍歷所有點，會超時，需要用到【優(yōu)先隊列】。
——因此這里邊集使用鄰接表（類型為List<int[]>[]，List數(shù)組，數(shù)組中的元素表示從下標i出發(fā)的邊，每條邊類型為int[]{u, w}）加入優(yōu)先隊列的元素類型（離源點v0的邊）被設(shè)置為long[]{u, w}，方便優(yōu)先隊列比較（map不能處理）
(3) 【魔法值結(jié)果】、以及【離1號城市的最短時間（dist數(shù)組中的值）】可能會超出Integer的范圍。
import java.util.Scanner;
import java.util.*;
// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {
// 到達1的邊（優(yōu)先隊列），為了快速找到最小邊【包含我們新增的不存在的捷徑】
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;
// 對應迪杰斯特拉已經(jīng)求出（離源點）最短路徑的點集
private static boolean[] used;
// 對應迪杰斯特拉的距離數(shù)組（離源點的距離）
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]; // 定義泛型數(shù)組，聲明和開辟空間要同時，這樣才能類型推斷（如果分開，編譯時會進行類型擦除）
adj = adjTmp;
for(int i=1; i<=n; i++){
adj[i] = new ArrayList<int[]>();
}
// 構(gòu)造邊
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});
}
// ----------利用迪杰斯特拉思想---------
// 已經(jīng)求得最短距離的點集
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});
// 執(zhí)行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已經(jīng)找到離源點最短路徑
// 更新和time[v]相關(guān)的邊（v作為used集合中新的中間點，更新另一個集合的time）
// 不需要更新另一個集合的所有點，只需要更新另一個集合中它的一跳鄰居（因為另一個集合中其他受影響點，后面會更新）
for (int[] jArr:adj[v]) {
int j = jArr[0];
if (!used[j]) {
long timeTmp = jArr[1] + dist[v];
// 加入優(yōu)先隊列
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));
}
// 從優(yōu)先隊列中拿最小邊
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;
}
}
