RT。

在 POJ2449 上死活过不去，现在是 MLE 状态，但是在 P2901 上过了。

现在不确定是不是算法原理的锅。。。

#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;

#define ll long long

const int N = 1010, M = 100010;
int n, m, S, T, K;
int hd[N], ed[M], nt[M], co[M], cnt;
int dis[N][N];
bool vis[N][N];

struct node
{
    int d, l, u;
    bool operator <(const node a) const
    {
        return d > a.d;
    }
};

priority_queue<node> pq;

void add_edge (int u, int v, int w)
{
    ed[++cnt] = v;
    co[cnt] = w;
    nt[cnt] = hd[u];
    hd[u] = cnt;
}

void dijkstra()
{
    memset (dis, 0x3f, sizeof dis);
    dis[S][0] = 0;
    node tmp = {0, 0, S};
    pq.push (tmp);
    while (!pq.empty())
    {
        int u = pq.top().u;
        int l = pq.top().l;
        int d = pq.top().d;
        pq.pop();
        if (vis[u][l])
            continue;
        vis[u][l] = 1;
        for (int i = hd[u]; i; i = nt[i])
        {
            int v = ed[i];
            int w = co[i] + d;
            int p = -1;
            for (int k = l; k < K; k++)
            {
                if (dis[v][k] >= w)
                {
                    p = k;
                    break;
                }
            }
            if (p != -1)
            {
                for (int k = K - 1; k > p; k--)
                {
                    dis[v][k] = dis[v][k - 1];
                    node tmp = {dis[v][k], k, v};
                    pq.push (tmp);
                }
                dis[v][p] = w;
                node tmp = {w, p, v};
                pq.push (tmp);
            }
        }
    }
}

int main()
{
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf ("%d%d%d", &u, &v, &w);
        add_edge (u, v, w);
    }
    scanf ("%d%d%d", &S, &T, &K);
    if (S == T)
        K++;
    dijkstra();
    if (dis[T][K - 1] == 0x3f3f3f3f)
        puts ("-1");
    else
        printf ("%d\n", dis[T][K - 1]);
    return 0;
}