给定一张 $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 \le S,T \le N \le 1000$,
$0 \le M \le 10^4$,
$1 \le K \le 1000$,
$1 \le L \le 100$

输入样例：

2 2
1 2 5
2 1 4
1 2 2

输出样例：

14

#include <queue>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1010, M = 2e4 + 10;

#define x first
#define y second

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

int e[M], ne[M], head[N], rhead[N], w[M], idx;
int dist[N];
bool st[N];
int cnt[N];
int n, m, S, T, K;

void add(int *head, int x, int y, int z)
{
    e[idx] = y;
    ne[idx] = head[x];
    w[idx] = z;
    head[x] = idx ++;
}

void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;
    heap.push({0, T});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        if (st[t.second]) continue;

        st[t.second] = true;

        for (int i = rhead[t.second]; i != -1; i = ne[i])
        {
            int j = e[i];

            if (dist[j] > dist[t.second] + w[i])
            {
                dist[j] = dist[t.second] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int bfs()
{
    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, dis = t.y.x;

        cnt[ver] ++;

        if (cnt[T] == K)
            return dis;

        for (int i = head[ver]; i != -1; i = ne[i])
        {
            int j = e[i];

            if (cnt[j] < K)
                heap.push({dis + dist[j] + w[i],{dis + w[i], j}});
        }
    }

    return -1;

}

int main()
{
    cin >> n >> m;

    memset(head, -1, sizeof head);
    memset(rhead, -1, sizeof rhead);

    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(head, a, b, c), add(rhead, b, a, c);
    }

    cin >> S >> T >> K;
    if (S == T)
        K ++;

    dijkstra();

    cout << bfs();

    return 0;
}