参考思路
这里距离d是指边的长度
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define x first
#define y second
typedef pair<int ,int> pii;
typedef pair<int, pii> piii;
const int N=1010, M=200010;
int n,m, S,T,K;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dist[N];
int st[N];
int cnt[N];//不加就tle
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;
heap.push({0, T});
memset(dist, 0x3f, sizeof dist);
dist[T]=0;
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.y;
if(st[ver])continue;
st[ver]=true;
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});
}
}
}
}
int astar(){
priority_queue<piii, vector<piii>, greater<piii>> heap;
heap.push({dist[S], {0, S}});
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.y.y, distance=t.y.x;
cnt[ver]++;
if(cnt[T]==K)return distance;
for(int i=h[ver]; ~i; i=ne[i]){
int j=e[i];
if(cnt[j]<K)
heap.push({distance+w[i]+dist[j], {distance+w[i], j}});
}
}
return -1;
}
int main(){
scanf("%d%d", &n, &m);
memset(h,-1, sizeof h);
memset(rh, -1, sizeof rh);
for(int i=0; i<m; i++){
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++;//多了一条为0的最短路
dijkstra();
printf("%d\n", astar());
return 0;
}