传送门

题意&简要做法

一张有向图，求出最多的互不相同的路径，满足路径长度之和\(\leq E\)。

可以转化为求K短路。注意这里不需要二分，只要不断取得剩下的路径里的最短路，累加权值直到超过E即可。

细节

原题&洛谷上有256M空间，BZOJ上只有64M，坑啊...

加入一些剪枝，在当前路径长度>E时直接不加入。

将double的值乘上一个很大的数，转换成long long，跑得快了一点，据说可以避免一些精度误差。

代码

#include 
    
     using namespace std;typedef long long ll;const int MAXN=5005, MAXM=400005;const ll INF=0x3f3f3f3f3f3f3f3f;int N, M, ne, in[MAXN];ll V, d[MAXN];struct Edge{Edge *nxt; int to; ll w;}E[MAXM],*hd[MAXN],*hr[MAXN];void adde(int u, int v, ll w){    E[ne].to=v;E[ne].w=w;E[ne].nxt=hd[u];hd[u]=&E[ne++];    E[ne].to=u;E[ne].w=w;E[ne].nxt=hr[v];hr[v]=&E[ne++];}struct St{    int u; ll g;    St(){}    St(int u, ll g):u(u),g(g){}    bool operator<(const St &o)const{return g+d[u]>o.g+d[o.u];}};void spfa(){    memset(d,0x3f,sizeof(d)); d[N]=0;    queue
     
       q; q.push(N);    while(!q.empty()){        int u=q.front(); q.pop(); in[u]=0;        for(Edge *e=hr[u]; e; e=e->nxt){            int v=e->to;            if(d[v]>d[u]+e->w){                d[v]=d[u]+e->w;                if(!in[v]) in[v]=1,q.push(v);            }        }    }}void As(){    priority_queue
      
        pq; pq.push(St(1,0));    int k=0;    while(!pq.empty()){        St s=pq.top(); pq.pop();        if(s.u==N){            ll f=s.g+d[s.u];            if(V>=f) V-=f, k++;            else break;        }else{            for(Edge *e=hd[s.u]; e; e=e->nxt){                ll g=s.g+e->w;                if(g+d[e->to]<=V) pq.push(St(e->to,g));            }        }    }    printf("%d\n", k);}int main(){    double t;    scanf("%d%d%lf", &N, &M, &t); V=(ll)(t*1e10+0.5);    for(int i=0,u,v; i