题目大意：给定一个值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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define M 5050using 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
          
            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
           
            (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
            
             (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<
             
              <