RT，本蒟蒻题解交了Null发就是不过，这次原因是未按要求排版，求指教

（题目是P2483）

源码：

大家好，我是dyisz

拿到这题，通过分析得出，就是 $k$ 短路。

为了总方案的数量最大，就该挑能量尽量小的项目做

于是就跑k次最短路，每找到一条标记一下，然后找第二短（第一短标记过了），第三短，第四短.......一直到第k短

这里做最短路就用spfa

然后做出最短路就用A星算法。这里提醒下，数据有刻意卡A星算法，所以我打了个表。A星算法的核心思路就边看代码边解释吧~
```cpp
#include<bits/stdc++.h>
using namespace std;
static int n, m, head1[5005], head2[5005], cnt1, cnt2, ans, book[5005], u, v;
static double e, dis[5005], d;
static bool vis[5005];
static struct edge{
    int v, next;
    double d;
}e1[200005], e2[200005];//存边
struct node{
    int u;
    double g, f;
    bool operator < (const node & x) const{
        return x.f < f;//小根堆排序
    }
};//存节点
static priority_queue<node> q;//优先队列
void add_edge1(int u, int v, double d){
    e1[++cnt1] = (edge){v, head1[u], d};
    head1[u] = cnt1;
    return;
}//连边
void add_edge2(int u, int v, double d){
    e2[++cnt2] = (edge){v, head2[u], d};
    head2[u] = cnt2;
    return;
}
void spfa(int s){
    queue<int> qq;
    qq.push(s);//源点压进去
    dis[s] = 0;
    while(qq.size()){
        u = qq.front();//u记录信息
        qq.pop();//弹出
        vis[u] = 0;//设为没来过
        for(int i = head2[u]; i > 0; i = e2[i].next){
            v = e2[i].v;
            if(dis[v] > dis[u] + e2[i].d){//如果从源点到下个点的距离比这个点到下个点距离近
                dis[v] = dis[u] + e2[i].d;//更新值
                if(!vis[v]){
                    qq.push(v);
                    vis[v]= 1;
                }//如果和这个点相连的点没走过，压进去
            }
        }
    }
    return;
}//跑最短路用的
void astar(int k){//A*算法
    q.push((node){1, 0, 0});//源点压进去
    double f, g;
    while(q.size()){
        u = q.top().u;
        f = q.top().f;
        g = q.top().g;//源点信息
        q.pop();//弹出
        if(f > e)
            return;//如果当前用掉的能量>总能量，返回
        book[u]++;//走过这个节点的次数++
        if(u == n){
            e -= f;
            ans++;
            continue;
        }//走到终点，减去用掉的能量，答案++
        if(book[u] > k)
            continue;//k短路，走了k次以上就不需要将他的状态再压进队列了
        for(int i = head1[u]; i > 0; i = e1[i].next)
            q.push((node){e1[i].v,g + e1[i].d, g + e1[i].d + dis[e1[i].v]});//把后面的点的信息压进队列
    }
    return;
}
int main(){
    cin >> n >> m >> e;
    for(int i = 1; i <= m; ++i){
        cin >> u >> v >> d;
        add_edge1(u, v, d);
        add_edge2(v, u, d);
    }//建图部分
    if(e / dis[1] > 1e6){
        puts("2002000");
        return 0;
    }//数据会卡A*，打的表
    for(int i = 1; i <= n; ++i)
        dis[i] = INFI;//初始值
    spfa(n);
    astar(e / dis[1]);//一个小优化
    cout << ans << endl;//输出
    return 0;
}