[文章目录]
Description
iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素……他给 iPig 带来了很多 1 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 N 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾……现在的你呀！ 注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。
2 <= N <= 5000，1 <= M <= 200000，1<=E<=107，1<=ei<=E
就是给你一个图，让你选最多条不同的路径，使得这些路径的长度和不超过e。
那么我们求出来所有的路径长度，从小向大选就是解了。我们知道dijkstra是每次选取一个距离源点最近且没有选过的点来更新答案。那么，假设我们不把答案更新（不覆盖掉原有的次优解），依然是每次选取最优的点，然后搜索其余点，扔到一个堆里（不将原有的覆盖掉）。那么，第i次堆顶元素为t的时候，就是到t的第i短路出现的时候。注意是堆顶元素的次数，不是t入堆的次数，因为有可能后面入堆的次优解在计算后比先前的更优。不过，如果就是将距离源点的长度当做评判标准的话，我们会不断更新任何一个由源点出发到任意节点的路径长度，假设到n的k短路为解，设长度为mx，那么所有由源点出发的路径都要排个序，比mx小的都会被计算到。所以我们换一个评判标准，A*算法。
A*，貌似思想就是期望更优的先找。 f=g+h f为评判标准，g为到该点的代价，h为到终点的估价。
我们将每个节点到n的最短路也纳入考虑，如果从堆顶拿出了一个元素，而它到n的最短路距离加上到源点的距离还不如其他元素，那么，当前就不更新它。这样，关于n的更优解被优先计算。再考虑正确性，如果元素在堆顶，并且为终点，那么说明对得的任何一个元素都不能优化到比堆顶更优的解。所以堆顶就为当前的最优解，得证。再考虑优化：如果一个节点已经出堆了k次，而到n的路径需要求出的条数不超过k。那么，就说明源点到该节点已经求出来了前k个短路径，就没有必要再将其放入堆中。另外0x42是double用于memset的较大值。
有待更新，感觉没有理解透彻。照着GXZlegend dalao拍了一遍代码，心中好不踏实，明天再好好理解一下。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<double , int> pr;
priority_queue<pr> q;
int n,m,cnt,cc,mx,head[5100],to[201000],nxt[201000],hh[5100],tt[201000],nn[201000];
double data[201000],dd[201000],e,dis[5100];
int num[5100];
bool vis[5100];
void add(int x,int y,double z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; data[cnt]=z;
tt[++cc]=x; nn[cc]=hh[y]; hh[y]=cc; dd[cc]=z;
}
double dijkstra()
{
memset(dis,0x42,sizeof(dis));
dis[n]=0; q.push(pr(0 , n));
while(!q.empty())
{
int x=q.top().second; q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=hh[x];i;i=nn[i])
if(dis[tt[i]]>dis[x]+dd[i])
dis[tt[i]]=dis[x]+dd[i],q.push(pr(-dis[tt[i]],tt[i]));
}
return dis[1];
}
int main()
{
scanf("%d%d%lf",&n,&m,&e);
int x,y;double z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%lf",&x,&y,&z);
add(x,y,z);
}
double tmp=dijkstra(); mx=(int) (e/tmp);
if(mx==0) {puts("0"); return 0;}
q.push(pr(-dis[1] , 1));
while(!q.empty())
{
x=q.top().second; z=-q.top().first; q.pop();
if(x==n)
{
if(z>e) break;
e-=z;
}
if(num[x]>=mx) continue;
num[x]++;
for(int i=head[x];i;i=nxt[i])
if(num[to[i]]<mx)
q.push(pr(-(z-dis[x]+data[i]+dis[to[i]]) , to[i]));
}
printf("%d\n",num[n]);
return 0;
}