题目描述
给定一张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≤105,
1≤K≤1000,
1≤L≤100
样例
输入样例:
2 2
1 2 5
2 1 4
1 2 2
输出样例:
14
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int ,int>PII;
typedef pair<int ,PII>PIII;
const int N=1010,M=200010;
int n,m;
int h[N],rh[N],e[M],w[M],ne[M],idx;
int dist[N],f[N],st[N];
int S,T,K;
void add(int *h,int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(){//建反图,找每个点到终点的最短路径
priority_queue<PII,vector<PII>,greater<PII>>heap;
memset(dist,0x3f,sizeof dist);
dist[T]=0;
heap.push({0,T});
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.second;
if(st[ver])continue;
st[ver]=1;
for(int i=rh[ver];~i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[ver]+w[i]){
dist[j]=dist[ver]+w[i];
heap.push({dist[j],j});
}
}
}
memcpy(f,dist,sizeof f);
}
int a_star(){//A*算法,堆排序时根据估价函数(即该点到终点的最短距离)加上真实值进行排序:f[s]+dist[t];
priority_queue<PIII,vector<PIII>,greater<PIII>>heap;
heap.push({f[S],{0,S}});
memset(st,0,sizeof st);
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.second.second,distance=t.second.first;
if(st[ver]>=K)continue;
st[ver]++;
if(ver==T&&st[ver]==K)return distance;
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(st[j]<K)
heap.push({distance+w[i]+f[j],{distance+w[i],j}});
}
}
return -1;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
memset(rh,-1,sizeof rh);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(h,a,b,c),add(rh,b,a,c);
}
scanf("%d%d%d",&S,&T,&K);
if(S==T)K++;
dijkstra();
printf("%d",a_star());
return 0;
}