萌新刚学OI玄关求条

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pi pair<int, int>

using namespace std;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 5e3 + 10, M = 2e5 + 10, D = 4e6 + 10;
double res, z, dis[N];
int n, m, x, y, tot, cnt, ans, rt[N], ch[D][2];
bool vis[N];
pair<double, pi> eg[M];
vector<int> add[N];
vector<pair<pi, double> > v[N];
priority_queue<pair<double, pi> > q;

inline int read() {
    char ch = getchar();
    int x = 0;
    bool t = 0;
    while (ch < '0' || ch > '9') t |= ch == '-', ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar();
    return t ? -x : x;
}

void dfs(int x) {
    vis[x] = true;
    int len = v[x].size();
    for (int i = 0; i < len; i++) {
        int y = v[x][i].first.first;
        double z = v[x][i].second;
        if (vis[y]) continue;
        if (fabs(dis[y] - dis[x] - z) <= eps) {
            v[x][i].first.second = 1;
            dfs(y);
        }
    }
    return;
}

int modify(int rt, int l, int r, int v) {
    int p = ++tot;
    if (l == r) return p;
    int mid = l + r >> 1;
    if (v <= mid) {
        ch[p][0] = modify(ch[rt][0], l, mid, v);
        ch[p][1] = ch[rt][1];
    } else {
        ch[p][1] = modify(ch[rt][1], mid + 1, r, v);
        ch[p][0] = ch[rt][0];
    }
    return p;
}

int queryfir(int rt, int l, int r) {
    if (l == r) return (rt ? l : 0);
    int mid = l + r >> 1;
    if (ch[rt][0])
        return queryfir(ch[rt][0], l, mid);
    else
        return queryfir(ch[rt][1], mid + 1, r);
}

int querynx(int rt, int l, int r, int v) {
    if (l == r) return (rt ? (l > v ? l : 0) : 0);
    int mid = l + r >> 1;
    if (mid <= v)
        return querynx(ch[rt][1], mid + 1, r, v);
    else {
        int tmp = querynx(ch[rt][0], l, mid, v);
        if (tmp) return tmp;
        return querynx(ch[rt][1], mid + 1, r, v);
    }
}

void dfs2(int x) {
    int len = add[x].size();
    for (int i = 0; i < len; i++) rt[x] = modify(rt[x], 1, cnt, add[x][i]);
    len = v[x].size();
    for (int i = 0; i < len; i++) {
        int y = v[x][i].first.first;
        if (v[x][i].first.second) {
            rt[y] = rt[x];
            dfs2(y);
        }
    }
    return;
}

signed main() {
    n = read(), m = read();
    scanf("%lf", &res);
    // cin >> res;
    for (int i = 1; i <= m; i++) {
        x = read(), y = read();
        // cin >> z;
        scanf("%lf", &z);
        if (x ^ n) v[y].push_back({{x, 0}, z});
    }
    for (int i = 1; i <= n - 1; i++) dis[i] = 1e12;
    q.push({0, {n, 0}});
    while (q.size()) {
        auto a = q.top();
        q.pop();
        int nw = a.second.first;
        if (vis[nw]) continue;
        vis[nw] = true;
        for (int i = 0; i < v[nw].size(); i++) {
            int y = v[nw][i].first.first;
            double z = v[nw][i].second;
            if (dis[y] > dis[nw] + z) {
                dis[y] = dis[nw] + z;
                q.push({-dis[y], {y, 0}});
            }
        }
    }
    memset(vis, false, sizeof vis);
    dfs(n);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < v[i].size(); j++) {
            int y = v[i][j].first.first;
            double z = v[i][j].second;
            if (!v[i][j].first.second) eg[++cnt] = {dis[i] + z - dis[y], {y, i}};
        }
    sort(eg + 1, eg + cnt + 1);
    for (int i = 1; i <= cnt; i++) add[eg[i].second.first].push_back(i);
    dfs2(n); 
    res -= dis[1], ans = 1;
    int tmp = queryfir(rt[1], 1, cnt);
    if (tmp) q.push({-eg[tmp].first, {1, tmp}});
    while (q.size()) {
        auto a = q.top();
        q.pop();
        double val = dis[1] - a.first;
        if (res - val <= -eps) break;
        res -= val;
        ans++;
        int c = a.second.first, d = a.second.second;
        int nx = querynx(rt[c], 1, cnt, d), tmp = eg[d].second.second;
        if (nx) q.push({a.first + eg[d].first - eg[nx].first, {c, nx}});
        nx = queryfir(rt[tmp], 1, cnt);
        if (nx) q.push({a.first - eg[nx].first, {tmp, nx}});
    }
    cout << ans << endl;
    return 0;
}