【模闆】第K短路

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct edge {
    int v, w, next;
} e1[100010], e2[100010];
int head1[1010], head2[1010], tot;
 
int n, m, k;
int dis[1010];
bool vis[1010];
 
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;
}
 
struct node {
    int id, f, g;
    node(int dd, int ff, int gg) {
	id = dd, f = ff, g = gg;
    }
    bool operator < (const node & x) const {
	if(x.f == f) return x.g < g;
	return x.f < f;
    }
};
 
void add(int u, int v, int w) {
    e1[++tot].v = v;
    e1[tot].w = w;
    e1[tot].next = head1[u];
    head1[u] = tot;
    e2[tot].v = u;
    e2[tot].w = w;
    e2[tot].next = head2[v];
    head2[v] = tot;
}
void spfa(int u) {
    queue<int> q;
    for(int i = 1; i <= n; i++) dis[i] = 1e9;
    dis[u] = 0;
    vis[u] = 1;
    q.push(u);
    while(!q.empty()) {
	u = q.front();
	q.pop();
	vis[u] = 0;
	for(int i = head2[u]; i; i = e2[i].next) {
	    int v = e2[i].v, w = e2[i].w;
	    if(dis[v] > dis[u] + w) {
		dis[v] = dis[u] + w;
		if(!vis[v]) {
		    vis[v] = 1;
		    q.push(v);
		}
            }
	}
    }
}
 
void A_star(int s, int t) {
    if(s == t) k++;
    priority_queue<node> q;
    q.push(node(s, 0, 0));
    int cnt = 0;
    while(!q.empty()) {
	node h = q.top();
	q.pop();
	if(h.id == t) {
	    if(++cnt == k) {
		printf("%d", h.f);
		return;
	    }
	}
	for(int i = head1[h.id]; i; i = e1[i].next) {
	    int v = e1[i].v, w = e1[i].w;
	    q.push(node(v, h.g + w + dis[v], h.g + w));
	}
    }
    puts("-1");
}
int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
	int u = read(), v = read(), w = read();
	add(u, v, w);
    }
    int s = read(), t = read();
    k = read();
    spfa(t);
    A_star(s, t);
    return 0;
}