题目描述
iPig在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒……。
能量守恒……iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素……等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多 1 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 N 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾……现在的你呀！
注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。
输入输出格式
输入格式：
第一行三个数 N、M、E 表示iPig知道的元素个数（元素从 1 到 N 编号）、iPig已经学会的魔法个数和iPig的总能量。
后跟 M 行每行三个数 $s_i$、$t_i$、$e_i$ 表示 iPig 知道一种魔法，消耗 $e_i$ 的能量将元素 $s_i$ 变换到元素 $t_i$ 。
输出格式：
一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。
输入输出样例
4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5
3
说明
有意义的转换方式共4种：
1->4，消耗能量 1.5
1->2->1->4，消耗能量 4.5
1->3->4，消耗能量 4.5
1->2->3->4，消耗能量 4.5显然最多只能完成其中的3种转换方式（选第一种方式，后三种方式仍选两个），即最多可以转换3份样本。 如果将 E=14.9 改为 E=15，则可以完成以上全部方式，答案变为 4。
数据规模
占总分不小于 10% 的数据满足 $N <= 6$，$M<=15$。
占总分不小于 20% 的数据满足 $N <= 100$，$M<=300$，$E<=100$且$E$和所有的$e_i$均为整数（可以直接作为整型数字读入）。
所有数据满足 $2 <= N <= 5000$，$1 <= M <= 200000$，$1<=E<=10^7$，$1<=e_i<=E$，$E$和$e_i$为实数。
解题思路
//本来想写一题左偏树练练手速的，百度一下就找到了这题，结果似乎没必要用左偏树。。。只是因为BZOJ很丧病，卡优先队列的内存，大家就纷纷选择了手写堆，某些大牛选择了左偏树当做可持久化堆，动态开点节省空间，而我这等蒟蒻用恒定大小的手写二叉堆的就够了…………
回归正题。
这题很容易看出来是求前k短路，是路径权值之和小于等于E，因为一种转化方式完成后就不能再用了，而为了尽量多地完成转换，肯定要选择当前转换代价最小(最短路、次短路、第3短路……)，转换完成一次(路径到达n点一次)就统计答案ans++，最后输出答案。
找k短路的算法最容易想到的是BFS暴搜，第k次搜到n点就是k短路。通过 百度一下 查阅资料我们学到了一种名叫A*的算法，用它可以求第K短路，证明不会，但是板子挺好背的，看几遍也就记住了……(2019年01月27日 更新 放一个月时间也就忘了)
A*有一个东西叫估价函数$f(n)$，$f(n)=g(n)+h(n)$，在求k短路的问题中，$g(n)$是从起点出发已经走了的长度，$h(n)$是从这个点到终点的最短路。
由于用到每个点到终点的最短路，我们可以在反向图上跑一遍spfa，求出终点到每个点的最短路，用dis[i]表示终点到第$i$号点的最短距离。
然后就可以跑A*了。
建立一个优先队列，每个元素为{d,u}，d=f(u)，优先队列是以d为键值的小根堆。
首先把{dis[1],1}/*即第一个点*/加入优先队列，然后进入如下循环——
(1) 从优先队列中取出d最小的节点u;
(2)如果u是终点n，那么就找到了一条k短路(第k次取出n点时的d就是第k短路路径长度)，E-=d，如果此时剩余的E>=0(浮点数判断可以用$1e-6$)，也就是有足够能量进行此次转换，那么ans++，否则能量不足，退出A*;
(3)拓展正向图中与u直接相连的点，并将它们入队(压入堆中)，设当前与u相连的点为v，边权为w，则新的$d=f(v)=f(u)-dis[u]+w+dis[v]$;
(4)如果堆空了，就退出A*，否则返回(1);
————————2018年5月13日更新————————
今天发现，这题在洛谷上被hack了……下面是92分代码，至于AC代码……我留坑吧
————————2019年10月6日更新————————
https://www.luogu.org/blog/cjyl/solution-p2483
原来说可并堆是因为要可持久化进行优化啊……现在看来下面的代码就是暴力……什么A*嘛
源代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,m,ans=;
double E; struct Edge{
int next,to;
double w;
}fe[],e[];//e存正向图，fe存反向图
int head[]={},cnt=,fhead[]={},fcnt=;//带f的都用于存反向图
void add(int u,int v,double w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;//给正向图加边 fe[fcnt].to=u;
fe[fcnt].w=w;
fe[fcnt].next=fhead[v];
fhead[v]=fcnt++;//给反向图加边
} double dis[];//裸spfa
bool inq[]={};
void spfa()
{
for(int i=;i<;i++) dis[i]=999999999.0;
dis[n]=0.0;
queue<int> q;
q.push(n);
inq[n]=;
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=;
for(int i=fhead[u];i;i=fe[i].next)
{
int v=fe[i].to;
double w=fe[i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(!inq[v])
{
inq[v]=;
q.push(v);
}
}
}
}
} struct Heap{
double d;
int u;
bool operator > (const Heap &a)const{
return d>a.d;
}
}heap[],temp;//手敲优先队列
int sz=;//优先队列内元素数量+1，个人比较喜欢这种表示方法
void pop()//删除堆顶，取出堆顶直接用heap[1]即可，我没写在pop()里
{
sz--;
heap[]=heap[sz];
heap[sz]={,};
int the=,son=;
while(son<sz)
{
if(heap[son]>heap[son+]&&son+<sz) son++;
if(heap[the]>heap[son]) swap(heap[the],heap[son]);
else break;
the=son;
son=the<<;
}
}
void push(double dd,int uu)//加入一个元素，dd=f(uu)，dd、uu防止变量名冲突
{
heap[sz]={dd,uu};
int the=sz++,fa=the>>;
while(fa)
{
if(heap[fa]>heap[the]) swap(heap[the],heap[fa]);
else break;
the=fa;
fa>>=;
}
} void astar()
{
push(dis[],);
while(sz>)
{
int u=heap[].u;
double dist=heap[].d;//取出堆顶
pop();//删除堆顶
if(u==n)//n点出队，说明找到一条k短路
{
E-=dist;
if(E>=1e-) ans++;
else return;
continue;
}
for(int i=head[u];i;i=e[i].next)//拓展与u相连的节点
{
int v=e[i].to;
double w=e[i].w;
push(dist-dis[u]+w+dis[v],v);
}
}
} int main()
{
//freopen("test.in","r",stdin);
scanf("%d%d%lf",&n,&m,&E);
for(int i=,u,v;i<=m;i++)
{
double w;
scanf("%d%d%lf",&u,&v,&w);
add(u,v,w);
}
spfa();
astar();
printf("%d\n",ans);
return ;
}