第K短路給定一張 N 個點編號 1,2…NM 條邊的有向圖求從起點 S 到終點 T 的第 K 短路的長度路徑允許重復(fù)經(jīng)過點或邊。注意每條最短路中至少要包含一條邊。輸入格式第一行包含兩個整數(shù) N 和 M。接下來 M 行每行包含三個整數(shù) A,B 和 L表示點 A 與點 B 之間存在有向邊且邊長為 L。最后一行包含三個整數(shù) S,T 和 K分別表示起點 S終點 T 和第 K 短路。輸出格式輸出占一行包含一個整數(shù)表示第 K 短路的長度如果第 K 短路不存在則輸出 ?1。數(shù)據(jù)范圍1≤S,T≤N≤1000,0≤M≤104,1≤K≤1000,1≤L≤100輸入樣例2 2 1 2 5 2 1 4 1 2 2輸出樣例14import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static int N1010,M10010,id1,id11,n,s,t,k; static boolean st[]new boolean[N];//dijkstra的輔助數(shù)組 static int f[]new int[N];//每個點的估計函數(shù) static int cnt[]new int[N];//每個點的彈出次數(shù) static int h[]new int[M]; static int e[]new int[M]; static int ne[]new int[M]; static int w[]new int[M]; static int h1[]new int[M]; static int e1[]new int[M]; static int ne1[]new int[M]; static int w1[]new int[M]; static BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int mInteger.parseInt(st.nextToken()); for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int aInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken()); int cInteger.parseInt(st.nextToken()); add(a,b,c); } stnew StringTokenizer(br.readLine()); sInteger.parseInt(st.nextToken());tInteger.parseInt(st.nextToken()); kInteger.parseInt(st.nextToken()); if(st){//此句一定要加 k; } //A*算法的思路是:在迪杰斯特拉算法的基礎(chǔ)之上 //把按距離來排序換成按距離估計函數(shù)的值來進行排序 //估計還說的是必須小于等于該點到真實終點的距離 也就是f(x)g(x) //第k個最短路的長度一定是大于最短的距離的 //f(x)0 的時候A* 算法就退化為了迪杰斯塔拉算法 //f(x)g(x) 的時候那么這樣的算法就是線性的 //所以我們的思路是建立一個優(yōu)先級隊列 排序順序是按距離估計函數(shù)的值來進行排序 //每次彈出隊頭元素 擴展所有與他所有相連的節(jié)點 //但是如果擴展到的節(jié)點已經(jīng)彈出去了k次那則不需要再進行擴展 //該點如果是第k次彈出 就是第k個最短路的長度 //估計函數(shù)的值我們可以先建立一張反向圖求出終點到各個點的最短距離 dijkstra(); if(f[s]Integer.MAX_VALUE){//提前判斷能否到達(dá) System.out.println(-1); return; } hightdijkstra(); bw.flush(); bw.close(); bw.close(); } static void hightdijkstra() throws IOException{ PriorityQueueint[] priorityQueuenew PriorityQueue((a,b)-Integer.compare(a[1]f[a[0]],b[1]f[b[0]])); priorityQueue.add(new int[]{s,0}); //在循環(huán)中 不能單純的用迪杰斯特拉中的dist 因為dist是不斷更新 變化的 while(!priorityQueue.isEmpty()){ int no[]priorityQueue.poll(); int uno[0]; cnt[u];//更新了幾次最短路徑了 if(ut cnt[u]k) { bw.write(no[1]); return; } for (int i h[u]; i 0; ine[i]) { int sone[i]; if(cnt[son]k){ //大于k條邊就不需要再進行擴展了 priorityQueue.add(new int[]{son,no[1]w[i]}); } } } bw.write(-1); } static void dijkstra(){ PriorityQueueint[] priorityQueuenew PriorityQueue((a,b)-a[1]-b[1]); priorityQueue.add(new int[]{t,0}); Arrays.fill(f, Integer.MAX_VALUE); f[t]0; while(!priorityQueue.isEmpty()){ int no[]priorityQueue.poll(); int uno[0]; if(!st[u]){ st[u]true; for (int i h1[u]; i 0; ine1[i]) { int sone1[i]; if(!st[son]){ if(f[son]f[u]w1[i]){ priorityQueue.add(new int[]{son,f[u]w1[i]}); f[son]f[u]w1[i]; } } } } } } static void add(int a,int b,int c){ e[id]b; ne[id]h[a]; w[id]c; h[a]id; e1[id1]a; ne1[id1]h1[b]; w1[id1]c; h1[b]id1; } }