注意点:
- 起点和终点相同时,k需要提前++.
- Node内的比较函数应当使用:当前费用+预估费用.
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=3e3,MAXM=3e5;
struct Edge_First{//反向图
int from,to,nxt,w;
}e_First[MAXM];
int head_First[MAXN],edgeCnt_First=1;
void addEdge_First(int u,int v,int w){
e_First[++edgeCnt_First].from=u;
e_First[edgeCnt_First].to=v;
e_First[edgeCnt_First].w=w;
e_First[edgeCnt_First].nxt=head_First[u];
head_First[u]=edgeCnt_First;
}
int s,t,k;//起点 终点 第k短路
struct Node_First{
int v,dis;
bool operator <(Node_First another)const{
return dis>another.dis;
}
};
int f[MAXN];//估价函数
void dijkstra(){
memset(f,0x3f,sizeof(f));
priority_queue<Node_First> q;
q.push(Node_First{t,0});
f[t]=0;
while(!q.empty()){
Node_First nowNode=q.top();
q.pop();
int nowU=nowNode.v;
if(nowNode.dis!=f[nowU])continue;
for(int i=head_First[nowU];i;i=e_First[i].nxt){
int nowV=e_First[i].to;
if(f[nowV]>f[nowU]+e_First[i].w){
f[nowV]=f[nowU]+e_First[i].w;
q.push(Node_First{nowV,f[nowV]});
}
}
}
}
struct Edge{
int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,int w){
e[++edgeCnt].from=u;
e[edgeCnt].to=v;
e[edgeCnt].w=w;
e[edgeCnt].nxt=head[u];
head[u]=edgeCnt;
}
struct Node{
int v,f,g;
bool operator <(Node another)const{
return f+g>another.f+another.g;
}
};
int updateTime[MAXN];
int ans;
bool Astar(){
priority_queue<Node> q;
q.push(Node{s,f[s],0});
while(!q.empty()){
Node nowNode=q.top();
q.pop();
int nowU=nowNode.v;
updateTime[nowU]++;
if(nowU==t&&updateTime[nowU]==k){
ans=nowNode.g;
return 1;
}
for(int i=head[nowU];i;i=e[i].nxt){
int nowV=e[i].to;
q.push(Node{nowV,f[nowV],nowNode.g+e[i].w});
}
}
return 0;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,l;
scanf("%d%d%d",&a,&b,&l);
addEdge_First(b,a,l);//反向边
addEdge(a,b,l);//正向边
}
scanf("%d%d%d",&s,&t,&k);
if(s==t)k++;
dijkstra();
if(Astar()){
cout<<ans<<endl;
}else cout<<"-1"<<endl;
return 0;
}