数据规模

题目里没给出数据规模，我从别的oj网址找的：
所有数据满足 2<=n<=5000 1<=m<=200000 1<=E<=1e7, 1<=ei<=E,所有的E和ei都为实数

用到的知识

最短路算法（spfa，dijkstra都可以）+可持久化堆

解题思路

此题可视为k短路题的模板，由于我讲的可能不是很好，这里推荐一个教程：俞鼎力大牛：堆的可持久化和k短路
由于该教程已经讲的比较细致了，所以我就简单地概括一下，看不懂的地方可以去看教程

构造最短路径树和边的分类

我们先从n点跑一遍最短路，这样就可以得到n为根的最短路径树，然后，我们就可以将边分为树边和非树边
如果一条边(从u到v边权为val)满足:d=val-dist[u]+dist[v],d==0（dist表示到n的距离，这个在跑最短路时可以得到）那么这条边就在树上，否则，d就是我们跑这条边（其他时候沿着树跑）比最短路多出来的距离这是一种情况
我们把所有非树边放到小根堆里，我们就可以得到第2，3短路，但是，这样我们得不到第k短路（k>=4），因为可能连着走两条非树边比走一条非树边更短，所以，我们要把非树边的集合也放进堆里

如何将所有非树边都放到堆里

首先，不是所有的非树边都可以放在同一个集合里的，只有满足一条边的终点在最短路径树上是另一条边的起点的子节点（理解不了可以画个图看看），才能把另一条边放入这条边所在的集合
那么，如何实现找出所有满足条件的集合呢？
我们可以对每个点开一个堆，装这个点出去的所有边，然后将这个点的边集合并到它的子节点上，依次往前合并即可。
注意这个堆的要求：
1.支持合并（左偏树）
2.可持久化（操作不会改变历史版本，即合并时，父节点的集合不受影响，只有子节点的集合受影响）
这就是可持久化左偏树
其实可持久化听起来很难，但是比起普通的左偏树，只是多了一行代码：

int merge(int x,int y){//合并x和y的堆 
    if(!x||!y)return x+y;//有一边为空则返回另一边
    if(tree[x].val>tree[y].val)swap(x,y);//小根堆 
    int p=++size;//与普通左偏树的不同
    tree[p]=tree[x];//可持久化操作,每次只影响新的树，不改变旧树 
    tree[p].rs=merge(tree[p].rs,y);//和右子树合并 
    if(tree[tree[p].ls].len<tree[tree[p].rs].len)swap(tree[p].ls,tree[p].rs);//保持左偏
    tree[p].len=tree[tree[p].rs].len+1;//更新子树长度 
    return p; 
}

总结

至此，我们已经知道该如何解决k短路问题了，具体步骤如下：
1.从终点跑一遍最短路，得到所有点里终点的距离，并建立最短路径树
2.将每个点的非树边放入这个点的可持久化左偏树中
3.将父亲节点的可持久化左偏树（堆里装与最短路相比需要的额外距离）并入子节点的可持久化左偏树中
4.将起点的可持久化左偏树放入一个堆（普通的小根堆或者小根优先队列都行）
5.每次取堆顶元素，计算得到第k短路，然后将替换一条边和加一条边的额外距离入堆

完整代码

//题目为魔法猪学院 
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx_n=5010;
const int mx_m=202002;
int n,m;
double energe;
double dist[mx_n];//到t的距离
struct Edge{
    double val;
    int u,v,next;
};
struct Graph{
    int head[mx_n],top;
    Edge edge[mx_m];
    void addedge(int u,int v,double val){
        edge[++top].val=val;
        edge[top].v=v;
        edge[top].u=u;
        edge[top].next=head[u];
        head[u]=top;
    }
}G,R;//正向图，反向图 
//dijkstra求出dist 
struct cmp{
    bool operator () (const int &a,const int &b)const{
        return dist[a]>dist[b];//小根堆 
    }
};
int nxt[mx_n];//最短路径树上u的下一跳边的编号为nxt[u] 
bool vis[mx_n];
void dijkstra(){
    memset(dist,127,sizeof(dist));
    priority_queue<int,vector<int>,cmp>q;
    q.push(n); //反向跑最短路 
    dist[n]=0;
    while(!q.empty()){
        int u=q.top();
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=R.head[u];i;i=R.edge[i].next){
            int v=R.edge[i].v;
            if(dist[v]>dist[u]+R.edge[i].val){
                dist[v]=dist[u]+R.edge[i].val;
                nxt[v]=i;
                q.push(v);
            }
        }
    }
}
//可持久化左偏树
int root[mx_n]; 
int size=0;
struct Tree{
    double val;//权值(走这条路比最短路长val) 
    int rs,ls;//右，左儿子
    int last;//最后一条不在最短路径树上的边的终点 
    int len;//子树长度 
}tree[mx_m*20];//左偏树（可持久化，空间为原来的logn倍，参考主席树） 
int Newtree(double val,int v){//新建一个树（点） 
    int x=++size;
    tree[x].ls=tree[x].rs=tree[x].len=0;
    tree[x].val=val;
    tree[x].last=v;
    return x;
}
int merge(int x,int y){//合并x和y的堆 
    if(!x||!y)return x+y;//有一边为空则返回另一边
    if(tree[x].val>tree[y].val)swap(x,y);//小根堆 
    int p=++size;
    tree[p]=tree[x];//可持久化操作,每次只影响新的树，不改变旧树 
    tree[p].rs=merge(tree[p].rs,y);//和右子树合并 
    if(tree[tree[p].ls].len<tree[tree[p].rs].len)swap(tree[p].ls,tree[p].rs);//保持左偏
    tree[p].len=tree[tree[p].rs].len+1;//更新子树长度 
    return p; 
} 
struct Path{//优先队列中的路径 
    int last;//路径上最后一个不在最短路径树上的边 
    double ans;//路径的长度(比最短路长的部分) 
    friend bool operator < (const Path &a,const Path &b){
        return a.ans>b.ans;
    }
}; 
//按距离排序，离终点越近越靠前 
int sor[mx_n];//用于按距离排序的数组 
bool CMP (int &a,int &b){
    return dist[a]<dist[b];
}
//main函数
int main(){
    scanf("%d%d%lf",&n,&m,&energe);
    for(int i=1;i<=m;++i){
        int u,v;
        double val;
        scanf("%d%d%lf",&u,&v,&val);
        if(u==n)continue;//起点为n的边是没用的边 
        R.addedge(v,u,val);
        G.addedge(u,v,val);
    }
    dijkstra();
    //从n开始反向跑最短路，生成最短路径树
    for(int i=1;i<=n;++i)sor[i]=i;
    sort(sor+1,sor+1+n,CMP);//按离终点的距离排序，使得子节点的堆先算完，再并入父节点的堆中 
    for(int i=1;i<=n;++i){
        int u=sor[i];
        for(int j=G.head[u];j;j=G.edge[j].next){
            //只要不在最短路径树上，就把这条边放入该点的堆里 
            int v=G.edge[j].v;
            if(nxt[u]!=j)root[u]=merge(root[u],Newtree(G.edge[j].val+dist[v]-dist[u],v));
        }
        if(G.edge[nxt[u]].v)root[u]=merge(root[u],root[G.edge[nxt[u]].v]);
        //父亲节点的堆要并入子节点的堆里 
    } 
    if(dist[1]>energe){//最短路比energe大 
        printf("0");
        return 0;
    }
    energe-=dist[1];
    int ans=1;//最短路算一种方案 
    priority_queue<Path>q;
    if(root[1])q.push((Path){root[1],tree[root[1]].val});//起点的堆中有所有点的堆 
    while(!q.empty()){
        Path now=q.top();
        q.pop();
        if(energe<now.ans+dist[1])break;
        ans++;
        energe-=now.ans+dist[1];
        int x=now.last;//最后一条不在最短路径树上的边
        //左右子树：替换最后一条不在最短路径树上的边 
        if(tree[x].ls){
            q.push((Path){tree[x].ls,now.ans-tree[x].val+tree[tree[x].ls].val});
        }
        if(tree[x].rs){
            q.push((Path){tree[x].rs,now.ans-tree[x].val+tree[tree[x].rs].val});
        }
        //堆顶：新增一条最小的边
        if(root[tree[x].last]){
            q.push((Path){root[tree[x].last],now.ans+tree[root[tree[x].last]].val}); 
        }
    }
    printf("%d",ans);
    return 0;
}

为了防止你看不懂，我写了很多注释！

吐槽

这题的数据是不是太弱了点，我dijkstra的优先队列写出大根堆都有30分（就是这里，我检查了几个小时硬是没检查出来）

魔法猪学院___题解