A*-第K短路
第K短路
给定一张 N 个点（编号 1,2…N），M 条边的有向图，求从起点 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 N=1010,M=10010,id=1,id1=1,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 br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int m=Integer.parseInt(st.nextToken()); for (int i = 0; i < m; i++) { st=new StringTokenizer(br.readLine()); int a=Integer.parseInt(st.nextToken()),b=Integer.parseInt(st.nextToken()); int c=Integer.parseInt(st.nextToken()); add(a,b,c); } st=new StringTokenizer(br.readLine()); s=Integer.parseInt(st.nextToken());t=Integer.parseInt(st.nextToken()); k=Integer.parseInt(st.nextToken()); if(s==t){//此句一定要加 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{ PriorityQueue<int[]> priorityQueue=new 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 u=no[0]; cnt[u]++;//更新了几次最短路径了 if(u==t && cnt[u]==k) { bw.write(no[1]+""); return; } for (int i = h[u]; i > 0; i=ne[i]) { int son=e[i]; if(cnt[son]<k){ //大于k条边就不需要再进行扩展了 priorityQueue.add(new int[]{son,no[1]+w[i]}); } } } bw.write("-1"); } static void dijkstra(){ PriorityQueue<int[]> priorityQueue=new 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 u=no[0]; if(!st[u]){ st[u]=true; for (int i = h1[u]; i > 0; i=ne1[i]) { int son=e1[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++; } }
