原题

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 1010, M = 200010;

int n, m, S, T, K;
int dist[N], cnt[N];//记录某点被遍历了几次
bool st[N];
vector<PII>h[N];
vector<PII>rh[N];
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 = 0; i < rh[ver].size(); i++) {
			int j = rh[ver][i].x;
			int dis = rh[ver][i].y;
			if (dist[j] > dist[ver] + dis) {
				dist[j] = dist[ver] + dis;
				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] ++ ;//这个点被遍历的次数+1
		if (cnt[T] == K)//如果这就是终点的第K次遍历，返回距离
			return distance;

		for (int i = 0; i < h[ver].size(); i ++) {
			int j = h[ver][i].x;
			int dis = h[ver][i].y;
			if (cnt[j] < K)
				heap.push({distance + dis + dist[j], {distance + dis, j}});
		}
	}

	return -1;
}

int main() {
	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i ++ ) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		h[a].push_back({b, c});
		rh[b].push_back({a, c});
	}
	scanf("%d%d%d", &S, &T, &K);
	if (S == T)
		K ++ ;
	dijkstra();
	printf("%d\n", astar());

	return 0;
}