RT，参照的题解(对着手打的)

#include <bits/stdc++.h>
using namespace std;
struct Edge
{
    int next, to;
    double w;
};

struct Graph
{
    int tot, head[50005];
    Edge edge[200005];
    void add(int x, int y, double z)
    {
        edge[++tot] = (Edge){head[x], y, z};
        head[x] = tot;
    }
} G, R;

int n, m, ans = 0;
double E;

struct Node
{
    int No;
    double dis;
    friend bool operator<(Node x, Node y)
    {
        return x.dis > y.dis;
    }
};

int vis[50005], fa[50005];
double dis[50005];

//标准的迪杰斯特拉
void dijkstra()
{
    priority_queue<Node> que;
    que.push((Node){n, 0});
    memset(dis, 127, sizeof(dis));
    dis[n] = 0;
    while (!que.empty())
    {
        Node u = que.top();
        que.pop();
        if (vis[u.No])
            continue;
        vis[u.No] = 1;
        for (int i = R.head[u.No]; i; i = R.edge[i].next)
        {
            Node v = (Node){R.edge[i].to, u.dis + R.edge[i].w};
            if (dis[v.No] > v.dis)
                dis[v.No] = v.dis, fa[v.No] = i, que.push(v);
        }
    }
}

int seq[50005], rt[50005];
bool cmp(int x, int y)
{
    return dis[x] < dis[y];
}

struct heap
{
    int left_son, right_son, dist, father;
    double value;
} tree[21 * 50005];

int cnt = 0;

int heap_add(int f, double value)
{
    int k = ++cnt;
    tree[k].left_son = tree[k].right_son = tree[k].dist = 0,
    tree[k].father = f,
    tree[k].value = value;
    return k;
}

int heap_merge(int x, int y)
{
    if (!x || !y)
        return x + y;
    if (tree[x].value - tree[y].value > 0)
        swap(x, y);
    int k = ++cnt;
    tree[k] = tree[x];
    tree[k].right_son = heap_merge(tree[k].right_son, y);
    if (tree[tree[k].left_son].dist < tree[tree[k].right_son].dist)
        swap(tree[k].left_son, tree[k].right_son);
    tree[k].dist = tree[tree[k].right_son].dist + 1;
    return k;
}

struct ing
{
    int x;
    double ans;
    friend bool operator<(ing x, ing y)
    {
        return x.ans > y.ans;
    }
};

int main()
{
    scanf("%d %d %lf", &n, &m, &E);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        double z;
        scanf("%d %d %lf", &x, &y, &z);
        if (x == n)
        {
            i--, m--;
            continue;
        }
        G.add(x, y, z);
        R.add(y, x, z);
    }

    dijkstra();

    for (int i = 1; i <= n; i++)
        seq[i] = i;
    sort(seq + 1, seq + n + 1, cmp);

    tree[0].dist = -1;
    for (int i = 1; i <= n; i++)
    {
        int u = seq[i];
        for (int j = G.head[u]; j; j = G.edge[j].next)
            if (fa[u] != j)
                rt[u] = heap_merge(rt[u], heap_add(G.edge[j].to, G.edge[j].w + dis[G.edge[j].to] - dis[u]));
        rt[u] = heap_merge(rt[u], rt[G.edge[fa[u]].to]);
    }

    priority_queue<ing> que;
    if (E - dis[1] < 0)
    {
        printf("0\n");
        return 0;
    }
    E -= dis[1], ans++;
    if (rt[1])
        que.push((ing){rt[1], tree[rt[1]].value});
    while (!que.empty())
    {
        ing u = que.top();
        if (E - (u.ans + dis[1]) < 0)
            break;
        E -= u.ans + dis[1], ans++;
        if (tree[u.x].left_son)
            que.push((ing){tree[u.x].left_son, u.ans - tree[u.x].value + tree[tree[u.x].left_son].value});
        if (tree[u.x].right_son)
            que.push((ing){tree[u.x].right_son, u.ans - tree[u.x].value + tree[tree[u.x].right_son].value});
        if (rt[tree[u.x].father])
            que.push((ing){rt[tree[u.x].father], u.ans + tree[rt[tree[u.x].father]].value});
    }

    printf("%d\n", ans);

    return 0;
}

#3、#4、#6 AC
#13 MLE 其余全WA
求大佬救救我 orz