题目大意：给定一个值E 求起点到终点的最多条路径 使长度之和不超过E

k短路的A*算法……每一个点有一个估价函数=g[x]+h[x] 当中g[x]是从源点出发已经走了的长度 h[x]是从这个点到汇点的最短路

首先先在反图上跑一遍SPFA求出每一个点的h[x]，然后将源点的g[x]+h[x]增加堆 每次取出堆顶时将堆顶的g[x]向所连接的边扩展 第k次取出汇点即是答案

当中有一个剪枝就是当第k+1次取出某个点时不继续拓展 防止MLE 可是这里k未知 我们能够对k进行估价处理 初始k=floor(E/最短路长度) 然后每次取出汇点时更新k k=cnt[n]+floor(E/当前路径长度)

比較丧病的是这题卡priority_queue……这东西的内存是手写堆的二倍 因为卡内存 所以会挂 能够手写堆 我写了可并堆+垃圾回收……

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 5050

using namespace std;

struct abcd{

    int pos;

    double g,h;

    bool operator < (const abcd &x) const

    {

        return g + h < x.g + x.h ;

    }

};

struct Heap{

    abcd num;

    Heap *ls,*rs;

    void* operator new (size_t size,int pos,double g,double h);

    void operator delete (void* p);

}*root,*mempool,*C;

struct edge{

    int to,next;

    double f;

}table[400400];

int head[M],tot=1;

bool flag;

queue<void*> bin;

int n,m,k,ans,cnt[M];

double e,f[M];

void* Heap :: operator new (size_t size,int pos,double g,double h)

{

    if( !bin.empty() )

    {

        Heap *re=(Heap*)bin.front();

        bin.pop();

        re->num.pos=pos;

        re->num.g=g;

        re->num.h=h;

        re->ls=re->rs=0x0;

        return re;

    }

    if(C==mempool)

    {

        C=new Heap[1<<15];

        mempool=C+(1<<15);

    }

    C->num.pos=pos;

    C->num.g=g;

    C->num.h=h;

    C->ls=C->rs=0x0;

    return C++;

}

void Heap :: operator delete (void *p)

{

    bin.push(p);

}

Heap* Merge(Heap *x,Heap *y)

{

    if(!x) return y;

    if(!y) return x;

    if( y->num < x->num )

        swap(x,y);

    if(flag^=1)

        x->ls=Merge(x->ls,y);

    else

        x->rs=Merge(x->rs,y);

    return x;

}

inline void Insert(int pos,double g,double h)

{

    root=Merge(root,new (pos,g,h) Heap);

}

inline void Pop()

{

    delete root;

    root=Merge(root->ls,root->rs);

}

void Add(int x,int y,double z)

{

    table[++tot].to=y;

    table[tot].f=z;

    table[tot].next=head[x];

    head[x]=tot;

}

void SPFA()

{

    static int q[1<<16];

    static unsigned short r,h;

    static bool v[M];

    int i;

    memset(f,0x42,sizeof f);

    f[n]=0;q[++r]=n;

    while(r!=h)

    {

        int x=q[++h];v[x]=0;

        for(i=head[x];i;i=table[i].next)

            if( i&1 && f[table[i].to]>f[x]+table[i].f )

            {

                f[table[i].to]=f[x]+table[i].f;

                if(!v[table[i].to])

                    v[table[i].to]=1,q[++r]=table[i].to;

            }

    }

}

void A_Star()

{

    int i;

    k=static_cast<int>(e/f[1])+1;

    Insert(1,0,f[1]);

    while(root)

    {

        abcd x=root->num;Pop();

        if( ++cnt[x.pos]>k )

            continue;

        if(x.pos==n)

        {

            if(e-x.g<0) return ;

            e-=x.g;++ans;

            k=cnt[n]+static_cast<int>(e/x.g)+1;

        }

        for(i=head[x.pos];i;i=table[i].next)

            if(~i&1)

                Insert(table[i].to,x.g+table[i].f,f[table[i].to]);

    }

}

int main()

{

    int i,x,y;

    double z;

    cin>>n>>m>>e;

    for(i=1;i<=m;i++)

    {

        scanf("%d%d%lf",&x,&y,&z);

        Add(x,y,z);

        Add(y,x,z);

    }

    SPFA();

    A_Star();

    cout<<ans<<endl;

    return 0;

}