#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
constexpr int MAXN = 200010;
int n, m, s, t, k, x, y, ww, cnt, fa[MAXN];

struct Edge {
  int cur, h[MAXN], nxt[MAXN], p[MAXN], w[MAXN];

  void add_edge(int x, int y, int z) {
    cur++;
    nxt[cur] = h[x];
    h[x] = cur;
    p[cur] = y;
    w[cur] = z;
  }
} e1, e2;

int dist[MAXN];
bool tf[MAXN], vis[MAXN], ontree[MAXN];

struct node {
  int x, v;

  node* operator=(node a) {
    x = a.x;
    v = a.v;
    return this;
  }

  bool operator<(node a) const { return v > a.v; }
} a;

priority_queue<node> Q;

void dfs(int x) {
  vis[x] = true;
  for (int j = e2.h[x]; j; j = e2.nxt[j])
    if (!vis[e2.p[j]])
      if (dist[e2.p[j]] == dist[x] + e2.w[j])
        fa[e2.p[j]] = x, ontree[j] = true, dfs(e2.p[j]);
}

struct LeftistTree {
  int cnt, rt[MAXN], lc[MAXN * 20], rc[MAXN * 20], dist[MAXN * 20];
  node v[MAXN * 20];

  LeftistTree() { dist[0] = -1; }

  int newnode(node w) {
    cnt++;
    v[cnt] = w;
    return cnt;
  }

  int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (v[x] > v[y]) swap(x, y);
    int p = ++cnt;
    lc[p] = lc[x];
    v[p] = v[x];
    rc[p] = merge(rc[x], y);
    if (dist[lc[p]] < dist[rc[p]]) swap(lc[p], rc[p]);
    dist[p] = dist[rc[p]] + 1;
    return p;
  }
} st;

void dfs2(int x) {
  vis[x] = true;
  if (fa[x]) st.rt[x] = st.merge(st.rt[x], st.rt[fa[x]]);
  for (int j = e2.h[x]; j; j = e2.nxt[j])
    if (fa[e2.p[j]] == x && !vis[e2.p[j]]) dfs2(e2.p[j]);
}

int main() {
  scanf("%d%d%d%d%d", &n, &m, &s, &t, &k);
  for (int i = 1; i <= m; i++)
    scanf("%d%d%d", &x, &y, &ww), e1.add_edge(x, y, ww), e2.add_edge(y, x, ww);
  Q.push({t, 0});
  while (!Q.empty()) {
    a = Q.top();
    Q.pop();
    if (tf[a.x]) continue;
    tf[a.x] = true;
    dist[a.x] = a.v;
    for (int j = e2.h[a.x]; j; j = e2.nxt[j]) Q.push({e2.p[j], a.v + e2.w[j]});
  }
  if (k == 1) {
    if (tf[s])
      printf("%d\n", dist[s]);
    else
      printf("-1\n");
    return 0;
  }
  dfs(t);
  for (int i = 1; i <= n; i++)
    if (tf[i])
      for (int j = e1.h[i]; j; j = e1.nxt[j])
        if (!ontree[j])
          if (tf[e1.p[j]])
            st.rt[i] = st.merge(
                st.rt[i],
                st.newnode({e1.p[j], dist[e1.p[j]] + e1.w[j] - dist[i]}));
  for (int i = 1; i <= n; i++) vis[i] = false;
  dfs2(t);
  if (st.rt[s]) Q.push({st.rt[s], dist[s] + st.v[st.rt[s]].v});
  while (!Q.empty()) {
    a = Q.top();
    Q.pop();
    cnt++;
    if (cnt == k - 1) {
      printf("%d\n", a.v);
      return 0;
    }
    if (st.lc[a.x])  
      Q.push({st.lc[a.x], a.v - st.v[a.x].v + st.v[st.lc[a.x]].v});
    if (st.rc[a.x])
      Q.push({st.rc[a.x], a.v - st.v[a.x].v + st.v[st.rc[a.x]].v});
    x = st.rt[st.v[a.x].x];
    if (x) Q.push({x, a.v + st.v[x].v});
  }
  printf("-1\n");
  return 0;
}

CE代码如上，使用可持久化合并堆优化。

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr int MAXN = 5010;
constexpr int MAXM = 400010;
constexpr double inf = 2e9;
int n, m, k, u, v, cur, h[MAXN], nxt[MAXM], p[MAXM], cnt[MAXN], ans;
int cur1, h1[MAXN], nxt1[MAXM], p1[MAXM];
double e, ww, w[MAXM], f[MAXN];
double w1[MAXM];
bool tf[MAXN];

void add_edge(int x, int y, double z) {  
  cur++;
  nxt[cur] = h[x];
  h[x] = cur;
  p[cur] = y;
  w[cur] = z;
}

void add_edge1(int x, int y, double z) { 
  cur1++;
  nxt1[cur1] = h1[x];
  h1[x] = cur1;
  p1[cur1] = y;
  w1[cur1] = z;
}

struct node {  
  int x;
  double v;

  bool operator<(node a) const { return v + f[x] > a.v + f[a.x]; }
};

priority_queue<node> q;

struct node2 {  
  int x;
  double v;

  bool operator<(node2 a) const { return v > a.v; }
} x;

priority_queue<node2> Q;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> e;
  while (m--) {
    cin >> u >> v >> ww;
    add_edge(u, v, ww);   
    add_edge1(v, u, ww);  
  }
  for (int i = 1; i < n; i++) f[i] = inf;
  Q.push({n, 0});
  while (!Q.empty()) {  
    x = Q.top();
    Q.pop();
    if (tf[x.x]) continue;
    tf[x.x] = true;
    f[x.x] = x.v;
    for (int j = h1[x.x]; j; j = nxt1[j]) Q.push({p1[j], x.v + w1[j]});
  }
  k = (int)e / f[1];
  q.push({1, 0});
  while (!q.empty()) { 
    node x = q.top();
    q.pop();
    cnt[x.x]++;
    if (x.x == n) {
      e -= x.v;
      if (e < 0) {
        cout << ans << '\n';
        return 0;
      }
      ans++;
    }
    for (int j = h[x.x]; j; j = nxt[j])
      if (cnt[p[j]] <= k && x.v + w[j] <= e) q.push({p[j], x.v + w[j]});
  }
  cout << ans << '\n';
  return 0;
}

100分Unaccept代码如上，使用A* 算法。