http://www.lydsy.com/JudgeOnline/problem.php?id=1975
https://www.luogu.org/problem/show?pid=2483
首先我们要想到把这题转化成求k短路
这个怎么说呢。。。先看题目一句话
iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数
既然要求每种转换方式都不相同，那就不可能是最短路然后贪心减了
不过还是可以贪心啊，既然最短路只能取一次，那我们就取次短路，再取第三短的路……直到不能取了为止
这好像很符合k短路的思想啊（说白了这题就是让你求这个k）
好了，现在成功地把问题转化了，那么问题是如何求这个k短路
明白一点的人都知道用A*轻松解决，那我说一下如何A*
首先我们从终点把边反向跑一遍最短路（SPFA或者dijkstra随便），记录每一个点的dist
然后从起点正向BFS，A*的估价函数也很显然
f(x)=BFS到此已走过的距离+从此到终点的最短路
然后把f(x)扔到堆里面，BFS取堆里f(x)最小的计算扩展即可
如果到终点计数一次
如果是求k短路的话只要计算第k次到终点时f(x)输出就好了
这题嘛到一次终点计数器+1，总能量减掉f(x)，直到不能减或者点已经跑完了输出计数器就能AC
关于这个堆的写法，我不推荐使用STL优先队列（这个真的会炸内存，不骗你）
毕竟手打二叉堆代码量又不大而且也很好打嘛
如果想要效率再高一些或者装个X之类的打个斜堆或者左偏树也可以啊
更强的还有可持久化堆或者平衡树（这个有人打过，详见XX一中俞鼎力dalao的：堆的可持久化和k短路）
反正我用二叉堆的啦啦啦
#include<bits/stdc++.h>
using namespace std;
struct heap{
double v;int x;
}h[4000001];
const double oo=1e9;
queue<int>q;
int cnt=0,hsum=0,n,m,s,t;
int nedge=0,p[200001],nex[200001],head[200001];
int nedge2=0,p2[200001],nex2[200001],head2[200001];
double c[200001],c2[200001],dist[10001],K;
bool vis[10001],jzq;
inline heap top(){return h[1];}
inline void push(heap p){
h[++hsum]=p;
for(int i=hsum;i>1;i/=2)if(h[i].v<=h[i/2].v)swap(h[i],h[i/2]);
else return;
}
inline void pop(){
h[1]=h[hsum--];
int ne;
for(int i=1;i<hsum&&i*2<=hsum;i=ne){
if(i*2+1<=hsum&&h[i*2].v>h[i*2+1].v)ne=i*2+1;
else ne=i*2;
if(h[ne].v<=h[i].v)swap(h[ne],h[i]);
else return;
}
}
inline void addedge(int x,int y,double z){
p[++nedge]=y;c[nedge]=z;
nex[nedge]=head[x];head[x]=nedge;
}
inline void addedge2(int x,int y,double z){
p2[++nedge2]=y;c2[nedge2]=z;
nex2[nedge2]=head2[x];head2[x]=nedge2;
}
inline void spfa(int x){
for(int i=1;i<=n;i++)dist[i]=oo;
memset(vis,0,sizeof vis);
dist[x]=0;vis[x]=1;q.push(x);
while(!q.empty()){
int now=q.front();q.pop();
for(int k=head2[now];k;k=nex2[k]){
if(dist[p2[k]]>dist[now]+c2[k]){
dist[p2[k]]=dist[now]+c2[k];
if(!vis[p2[k]]){
q.push(p2[k]);
vis[p2[k]]=1;
}
}
}
vis[now]=0;
}
}
inline void bfs(){
heap rp;rp.v=dist[s];rp.x=s;push(rp);
while(hsum){
rp=top();pop();
int x=rp.x;
for(int k=head[x];k;k=nex[k]){
heap pr=rp;pr.x=p[k];
pr.v=pr.v-dist[x]+c[k]+dist[p[k]];
push(pr);
}
if(x==t){
cnt++;
if(K<rp.v){
printf("%d",cnt-1);
jzq=0;
return;
}else K-=rp.v;
}
}
}
int main()
{
scanf("%d%d%lf",&n,&m,&K);
for(int i=1;i<=m;i++){
int x,y;double z;scanf("%d%d%lf",&x,&y,&z);
addedge(x,y,z);
addedge2(y,x,z);
}
jzq=1;
s=1;t=n;
spfa(t);
bfs();
if(jzq)printf("%d",cnt);
return 0;
}