题目描述
给定一张 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
算法1
都是y总的代码,改了几个地方
信息压缩替代pair
原图反图公用head
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=10010, M=200010;
int n,m,S,T,K;
int ver[M],edge[M],nxt[M],head[2*N],tot;
int dist[N],cnt[N];
bool pass[N];
void add(int x,int y,int z){
ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}
void dijkstra(){
priority_queue<int,vector<int>,greater<int>> heap;
heap.push(0*N+T);
memset(dist,0x3f,sizeof dist);
dist[T]=0;
while(heap.size()){
auto t=heap.top();
heap.pop();
int x=t%N;
if(pass[x])continue;
pass[x]=true;
for(int i=head[N+x];i;i=nxt[i]){
int y=ver[i];
if(dist[y]<=dist[x]+edge[i])continue;
dist[y]=dist[x]+edge[i];
heap.push(dist[y]*N+y);
}
}
}
int astar(){
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({dist[S],0*N+S});
while(heap.size()){
auto t=heap.top();
heap.pop();
int x=t.second%N,pathlen=t.second/N;
cnt[x]++;
if(cnt[T]==K)return pathlen;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(cnt[y]>=K)continue;
heap.push({dist[y]+edge[i]+pathlen,(pathlen+edge[i])*N+y});
}
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y+N,x,z);
}
cin>>S>>T>>K;
if(S==T)K++;
dijkstra();
cout<<astar()<<endl;
}