Rt.

这个问题已经困扰我五天了。若有大佬相助，必关！

#include <iostream>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

struct edge
{
	int next, to;
	long double w;
};

struct node
{
	int l, r, dis, w, u;
};

class edgepack
{
	public:
		int cur, head[5005];
		edge e[200005];
		inline void add(int u, int v, long double w)
		{
			++cur;
			e[cur] = {head[u], v, w};
			head[u] = cur;
		}
};

class Tree
{
	public:
		int cnt, root[5005];
		node tree[4000005];
		inline int insert(long double w, int u)
		{
			++cnt;
			tree[cnt].w = w;
			tree[cnt].u = u;
			return cnt;
		}
		int merge(int l, int r)
		{
			if (!l || !r)
			{
				return l | r;
			}
			++cnt;
			tree[cnt].l = tree[l].l;
			tree[cnt].w = tree[l].w;
			tree[cnt].u = tree[l].u;
			tree[cnt].r = merge(tree[cnt].r, r);
			if (tree[tree[cnt].l].dis < tree[tree[cnt].r].dis)
			{
				swap(tree[cnt].l, tree[cnt].r);
			}
			tree[cnt].dis = tree[tree[cnt].r].dis + 1;
			return cnt;
		}
};

bool vis1[5005], vis2[5005], flag[5005];
int n, m, x, y, ans, fa[5005];
long double E, w, dis[5005];
priority_queue<pair<long double, int>, vector<pair<long double, int> >, greater<pair<long double, int> > > q;
pair<long double, int> t;
edgepack e1, e2;
Tree tree;

inline void dijkstra1()
{
	q.push(make_pair(0, n));
	while (!q.empty())
	{
		t = q.top();
		q.pop();
		if (vis1[t.second])
		{
			continue;
		}
		vis1[t.second] = true;
		dis[t.second] = t.first;
		for (register int i = e2.head[t.second]; i; i = e2.e[i].next)
		{
			q.push(make_pair(t.first + e2.e[i].w, e2.e[i].to));
		}
	}
}

inline long double dijkstra2(int k)
{
	int cnt = 0;
	if (tree.root[1])
	{
		q.push(make_pair(dis[1] + tree.tree[tree.root[1]].w, tree.root[1]));
	}
	while (!q.empty())
	{
		t = q.top();
		q.pop();
		++cnt;
		if (cnt == k - 1)
		{
			return t.first;
		}
		if (tree.tree[t.second].l)
		{
			q.push(make_pair(t.first + tree.tree[tree.tree[t.second].l].w - tree.tree[t.second].w, tree.tree[t.second].l));
		}
		if (tree.tree[t.second].r)
		{
			q.push(make_pair(t.first + tree.tree[tree.tree[t.second].r].w - tree.tree[t.second].w, tree.tree[t.second].r));
		}
		x = tree.root[tree.tree[t.second].u];
		if (x)
		{
			q.push(make_pair(t.first + tree.tree[x].w, x));
		}
	}
	return -1;
}

void dfs1(int u)
{
	vis2[u] = true;
	for (register int i = e2.head[u]; i; i = e2.e[i].next)
	{
		x = e2.e[i].to;
		if (!vis2[x] && dis[u] + e2.e[i].w == dis[x])
		{
			fa[x] = u;
			flag[i] = true;
			dfs1(x);
		}
	}
}

void dfs2(int u)
{
	vis2[u] = true;
	if (fa[u])
	{
		tree.root[u] = tree.merge(tree.root[u], tree.root[fa[u]]);
	}
	for (register int i = e2.head[u]; i; i = e2.e[i].next)
	{
		x = e2.e[i].to;
		if (!vis2[x] && fa[x] == u)
		{
			dfs2(x);
		}
	}
}

inline long double kthpath(int k)
{
	while (!q.empty())
	{
		q.pop();
	}
	memset(vis1, false, sizeof(vis1));
	memset(vis2, false, sizeof(vis2));
	memset(flag, false, sizeof(flag));
	memset(fa, 0, sizeof(fa));
	memset(tree.root, 0, sizeof(tree.root));
	memset(tree.tree, 0, sizeof(tree.tree));
	for (register int i = 1; i <= n; ++i)
	{
		dis[i] = 0;
	}
	tree.cnt = 0;
	tree.tree[0].dis = -1;
	dijkstra1();
	if (k == 1)
	{
		if (vis1[1])
		{
			return dis[1];
		}
		else
		{
			return -1;
		}
	}
	dfs1(n);
	for (register int i = 1; i <= n; ++i)
	{
		if (vis1[i])
		{
			for (register int j = e1.head[i]; j; j = e1.e[j].next)
			{
				x = e1.e[j].to;
				if (!flag[j] && vis1[x])
				{
					tree.root[i] = tree.merge(tree.root[i], tree.insert(e1.e[j].w + dis[x] - dis[i], x));
				}
			}
		}
	}
	memset(vis2, false, sizeof(vis2));
	dfs2(n);
	return dijkstra2(k);
}

int main()
{
	cin >> n >> m >> E;
	while (m--)
	{
		cin >> x >> y >> w;
		e1.add(x, y, w);
		e2.add(y, x, w);
	}
	for (register int i = 1; E >= 0; ++i)
	{
		w = kthpath(i);
		if (w == -1)
		{
			break;
		}
		E -= w;
		++ans;
	}
	cout << ans << "\n";
	return 0;
}