题意给出一张nnn个点mmm条边的有向带权图求出最大的kkk满足前kkk短路径加长度起来大于EEE。n≤5010n\le5010n≤5010m≤2×105m\le2\times10^5m≤2×105E≤107E\le10^7E≤107边权w≤Ew\le Ew≤E。思路先用dijdijdij在反图上跑建一个以nnn为根的最短路树对于一个点uuu定义d(u)d(u)d(u)为uuu到nnn的最短路长度。对于一条边(u,v,w)(u,v,w)(u,v,w)定义祂的新权值w′wd(v)−d(u)wwd(v)-d(u)w′wd(v)−d(u)。对于一条路径把路径上的非最短路树边按照顺序领出来设为(u1,v1),(u2,v2),…(u_1,v_1),(u_2,v_2),\dots(u1​,v1​),(u2​,v2​),…那么对于每个iii有ui1u_{i1}ui1​是viv_ivi​在最短路树上的祖先而这条路径的边权和为d(s)d(s)d(s)加所有非最短路树边的新权值和。现在来考虑一个暴力在每个点uuu上存所有以uuu的某个祖先为起点的非最短路树边用一个优先队列存现在有哪些路经每次选最短的取出来并把祂能到直接达的所有点放进优先队列。显然这样是过不了的但是可以用可持久化可并堆优化。具体的每个点开可并小根堆存以这个点祖先为起点的所有非最短路树边。显然同一个堆中只有堆顶需要放进优先队列。在把一个路径取出来时只需要把祂在堆上的左右儿子和祂存的边能到达的点加入优先队列。代码// Problem: P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P2483// Memory Limit: 128 MB// Time Limit: 1000 ms//// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.husingnamespacestd;namespaceIO{templatetypenameTinlinevoidread(Tx){x0;charcgetchar();boolf0;while(!isdigit(c))c-?f1:0,cgetchar();while(isdigit(c))xx*10c-0,cgetchar();f?x-x:0;}templatetypenameTinlinevoidwrite(T x){if(x0){putchar(0);return;}x0?x-x,putchar(-):0;shortst[50],top0;while(x)st[top]x%10,x/10;while(top)putchar(st[top--]0);}inlinevoidread(charc){cgetchar();while(isspace(c))cgetchar();}inlinevoidwrite(charc){putchar(c);}inlinevoidread(doublex){scanf(%lf,x);}inlinevoidwrite(doublex){printf(%lf,x);}inlinevoidread(strings){s.clear();charc;read(c);while(!isspace(c)~c)sc,cgetchar();}inlinevoidwrite(string s){for(inti0,lens.size();ilen;i)putchar(s[i]);}templatetypenameTinlinevoidwrite(T*x){while(*x)putchar(*(x));}templatetypenameT,typename...T2inlinevoidread(Tx,T2...y){read(x),read(y...);}templatetypenameT,typename...T2inlinevoidwrite(constT x,constT2...y){write(x),putchar( ),write(y...),sizeof...(y)1?putchar(\n):0;}}usingnamespaceIO;constintmaxn5010,maxm200010;constdoubleeps1e-8;intn,m,fa[maxn],rt[maxn];doubleE,dis[maxn];structEDGE{intu,v;doublew;}b[maxm];vectorpairint,doublee[maxn],ef[maxn];vectorinttr[maxn];boolflag[maxn],in[maxn];namespaceLeftist_Tree{structnode{intch[2],dist,to;doubleval;}t[maxm*20];intcnt;intmerge(intu,intv){if(!u||!v)returnuv;if(t[u].valt[v].val)swap(u,v);intclonecnt;t[clone]t[u];t[clone].ch[1]merge(t[u].ch[1],v);if(t[t[clone].ch[0]].distt[t[clone].ch[1]].dist)swap(t[clone].ch[0],t[clone].ch[1]);t[clone].distt[t[clone].ch[1]].dist1;returnclone;}};voiddij(ints){priority_queuepairdouble,intq;for(inti1;in;i)dis[i]1e15;dis[s]0;q.push({0,s});while(!q.empty()){auto[l,u]q.top();q.pop();if(flag[u])continue;flag[u]1;for(auto[v,w]:ef[u])if(dis[v]dis[u]w)dis[v]dis[u]w,q.push({-dis[v],v});}}voiddfs(intu){for(intv:tr[u]){rt[v]Leftist_Tree::merge(rt[u],rt[v]);dfs(v);}}priority_queuepairdouble,int,vectorpairdouble,int,greaterpairdouble,intqu;signedmain(){read(n,m,E);for(inti1;im;i){intu,v;doublew;read(u,v,w);if(un)w1e15;e[u].push_back({v,w}),ef[v].push_back({u,w});b[i]{u,v,w};}dij(n);for(inti1;in;i)for(auto[v,w]:ef[i])if(abs(dis[v]-dis[i]-w)eps)fa[v]i;for(inti1;in;i)if(dis[i]1e14)in[i]1;for(inti1;im;i){auto[u,v,w]b[i];if((fa[u]vabs(dis[u]-(dis[v]w))eps))continue;wwdis[v]-dis[u];if(in[u]in[v]){intd;Leftist_Tree::t[dLeftist_Tree::cnt]{{0,0},0,v,w};if(rt[u]0)rt[u]d;elsert[u]Leftist_Tree::merge(rt[u],d);}}for(inti1;in;i)if(in[i]fa[i])tr[fa[i]].push_back(i);dfs(n);intans1;E-dis[1];qu.push({dis[1]Leftist_Tree::t[rt[1]].val,rt[1]});while(!qu.empty()){auto[l,u]qu.top();qu.pop();E-l;if(E0)break;ans;if(Leftist_Tree::t[u].ch[0])qu.push({l-Leftist_Tree::t[u].valLeftist_Tree::t[Leftist_Tree::t[u].ch[0]].val,Leftist_Tree::t[u].ch[0]});if(Leftist_Tree::t[u].ch[1])qu.push({l-Leftist_Tree::t[u].valLeftist_Tree::t[Leftist_Tree::t[u].ch[1]].val,Leftist_Tree::t[u].ch[1]});intdrt[Leftist_Tree::t[u].to];if(d)qu.push({lLeftist_Tree::t[d].val,d});}write(ans);return0;}