A*-第K短路

第K短路给定一张 N 个点编号 1,2…NM 条边的有向图求从起点 S 到终点 T 的第 K 短路的长度路径允许重复经过点或边。注意每条最短路中至少要包含一条边。输入格式第一行包含两个整数 N 和 M。接下来 M 行每行包含三个整数 A,B 和 L表示点 A 与点 B 之间存在有向边且边长为 L。最后一行包含三个整数 S,T 和 K分别表示起点 S终点 T 和第 K 短路。输出格式输出占一行包含一个整数表示第 K 短路的长度如果第 K 短路不存在则输出 −1。数据范围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的辅助数组 static int f[]new int[N];//每个点的估计函数 static int cnt[]new int[N];//每个点的弹出次数 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*算法的思路是:在迪杰斯特拉算法的基础之上 //把按距离来排序换成按距离估计函数的值来进行排序 //估计还说的是必须小于等于该点到真实终点的距离 也就是f(x)g(x) //第k个最短路的长度一定是大于最短的距离的 //f(x)0 的时候A* 算法就退化为了迪杰斯塔拉算法 //f(x)g(x) 的时候那么这样的算法就是线性的 //所以我们的思路是建立一个优先级队列 排序顺序是按距离估计函数的值来进行排序 //每次弹出队头元素 扩展所有与他所有相连的节点 //但是如果扩展到的节点已经弹出去了k次那则不需要再进行扩展 //该点如果是第k次弹出 就是第k个最短路的长度 //估计函数的值我们可以先建立一张反向图求出终点到各个点的最短距离 dijkstra(); if(f[s]Integer.MAX_VALUE){//提前判断能否到达 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}); //在循环中 不能单纯的用迪杰斯特拉中的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; } }