Rt.

我从未见过如此难的模版题，调了四天了……

蒟蒻第一次写可持久化左偏树，若犯了什么低级错误请大佬们勿喷。

代码：

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

using namespace std;

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

struct node
{
	int l, r, dis, to;
	double w;
};

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

class Tree
{
	public:
		int cnt, root[5005];
		node tree[4000005];
		int merge(int l, int r)
		{
			if (!l || !r)
			{
				return l + r;
			}
			if (tree[l].w < tree[r].w)
			{
				swap(l, r);
			}
			++cnt;
			tree[cnt].l = tree[l].l;
			tree[cnt].w = tree[l].w;
			tree[cnt].r = merge(tree[l].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;
		}
		inline int insert(double w, int to)
		{
			++cnt;
			tree[cnt].w = w;
			tree[cnt].to = to;
			return cnt;
		}
};

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

inline void dijkstra1()
{
	memset(Vis, false, sizeof(vis));
	for (register int i = 1; i < n; ++i)
	{
		dis[i] = 2e9;
	}
	dis[n] = 0;
	while (!q.empty())
	{
		q.pop();
	}
	q.push(make_pair(0, n));
	while (!q.empty())
	{
		t = q.top();
		q.pop();
		Vis[t.second] = true;
		for (register int i = e2.head[t.second]; i; i = e2.e[i].next)
		{
			x = e2.e[i].to;
			if (t.first + e2.e[i].w < dis[x])
			{
				dis[x] = t.first + e2.e[i].w;
				if (!Vis[x])
				{
					q.push(make_pair(dis[x], x));
				}
			}
		}
	}
}

inline double dijkstra2()
{
	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[t.second].w + tree.tree[tree.tree[t.second].l].w, tree.tree[t.second].l));
		}
		if (tree.tree[t.second].r)
		{
			q.push(make_pair(t.first - tree.tree[t.second].w + tree.tree[tree.tree[t.second].r].w, tree.tree[t.second].r));
		}
		x = tree.root[tree.tree[t.second].to];
		if (x)
		{
			q.push(make_pair(t.first + tree.tree[x].w, x));
		}
	}
	return -1;
}

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

void dfs2(int u)
{
	vis[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 (!vis[x] && u == fa[x])
		{
			dfs2(x);
		}
	}
}

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

int main()
{
	scanf("%d%d%lf", &n, &m, &E);
	while (m--)
	{
		scanf("%d%d%lf", &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;
	}
	printf("%d", ans - (n != 1));
	return 0;
}

这花红柳绿的评测结果看着非常漂亮