k短路
好像是一个比较简单的东西
对于 正权有向图，(displaystyle G=(V,E),V={V_i}_{i=1}^nE={(u_i,v_i,w_i)}_{i=1}^m)
求(s)到(t)的前(k)短路
考虑建立反图(G'=(V,E'))，容易( ext{Dijkstra})求得(t)的单源最短路(dis_i)，并且建立一棵最短路树
考虑(s ightarrow t)的最短路，一定是走了一些树边和非树边
选择一条非树边((u,v,w))会使长度增加(w'=w-(dis_u-dis_v))，称(w')为额外长度
考虑我们选择的非树边序列((u_i,v_i,w_i))，显然有：(u_{i+1})是(v_i)在最短路树上的祖先
考虑用搜索扩展的方式来遍历所有路径情况
记录当前的节点(u)，产生的额外长度(d)，则每次的扩展可以归纳为
1.从(u)所有祖先中取出边的集合(S_u)
2.依次遍历(S_u)中的所有边((u_i,v_i,w'_i))，进入递归(u'=v_i,d'=d+w'_i)
每次扩展会产生一个新的状态，且恰好可以遍历每一个状态一次
然而，为了求出前(k)短路，我们必须按照答案从小到大遍历
那么我们首先需要将集合(S_u)排序，从小到大遍历，其次要对于不同的递归情况按照大小扩展
容易想到用一个堆维护扩展的顺序，为了保存遍历(S_u)集合的过程，记录一个指针(p)
此时，用堆维护扩展的方法显然：
1.取出堆顶状态((u,d,p))
2.转移
2-1.在当前递归栈中移动(pleftarrow p+1)，改变(d)
2-2.模拟上面，建立新的递归栈，同时令指针为(0)
得到(u'=v_{u,p},d'=d+w'_{v,0},p'=0)
如果暴力处理出(S_u)，则预处理复杂度为(O(nmlog m))，状态扩展复杂度为(O(2klog k))
用可持久化可并堆处理(S_u)，(p)记录当前堆顶节点指针
每次扩展(pleftarrow lson_p)或者(pleftarrow rson_p)，增加一个扩展状态
则预处理复杂度以及空间复杂度为(O(mlog m))，状态扩展复杂度为(O(3klog k))
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cctype>
using namespace std;
typedef double db;
typedef pair <db,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
template <class T=int> T rd(){
T s=0; int f=0;
while(!isdigit(IO=getchar())) f|=IO=='-';
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=5010,M=2e5+10;
const db eps=1e-7,INF=1e18;
template <class T> class Heap{
public:
T val;
int h;
Heap *ls,*rs;
T top(){ return val; }
Heap(){}
Heap(Heap *x):val(x->val),h(x->h),ls(x->ls),rs(x->rs){ ; }
Heap(T val):val(val),h(0),ls(0),rs(0){ ; }
friend Heap* Union(Heap *x,Heap *y){
if(!x) return y;
if(!y) return x;
if(y->val<x->val) swap(x,y);
Heap* u=new Heap(x);
u->rs=Union(u->rs,y);
if(u->rs && (!u->ls || u->rs->h>u->ls->h)) swap(u->ls,u->rs);
u->h=u->rs?u->rs->h+1:1;
return u;
}
Heap* pop(){ return Union(ls,rs); }
friend Heap* push(Heap *u,T val){ return Union(u,new Heap(val)); }
};
typedef Heap <Pair> Node;
Node *rt[N];
struct Edge{
int to;db w;
Edge *nxt;
Edge(){}
Edge(int to,db w,Edge* nxt):to(to),w(w),nxt(nxt){ ; }
};
Edge *head[N],*pre[N];
void AddEdge(int u,int v,db w){
Edge* t=new Edge(v,w,head[u]);
head[u]=t;
}
int n,m,fa[N];
db E,dis[N];
void Dijkstra(int u){
static priority_queue <Pair,vector<Pair>,greater<Pair>> que;
rep(i,1,n) dis[i]=INF;
dis[u]=0,que.push({0,u});
while(!que.empty()){
int u=que.top().se;db d=que.top().fi; que.pop();
if(dis[u]<d-eps) continue;
for(Edge *i=head[u];i;i=i->nxt) {
int v=i->to;
if(dis[v]>dis[u]+i->w+eps) pre[v]=i,fa[v]=u,que.push({dis[v]=dis[u]+i->w,v});
}
}
}
void Construct(){
static int I[N];
rep(i,1,n) I[i]=i;
sort(I+1,I+n+1,[&](int x,int y){ return dis[x]<dis[y]; });
rep(u,1,n) {
for(Edge *i=head[u];i;i=i->nxt) {
int v=i->to;
if(pre[v]==i) continue;
rt[v]=push(rt[v],mp(i->w-(dis[v]-dis[u]),u));
}
}
rt[n]=0;
rep(j,1,n) {
int u=I[j];
rt[u]=Union(rt[u],rt[fa[u]]);
}
}
struct State{
db s;
Node *rt;
bool operator < (const State &__) const {
return s>__.s;
}
};
int ans;
void Kth_Path(){
static priority_queue <State> que;
if(dis[1]>E+eps) return void(puts("0"));
ans=1,E-=dis[1];
if(rt[1]) que.push({dis[1]+rt[1]->val.fi,rt[1]});
while(!que.empty()) {
State u=que.top(); que.pop();
if(u.s>E+eps) break;
int v=u.rt->val.se;
ans++,E-=u.s;
if(rt[v]) que.push({u.s+rt[v]->top().fi,rt[v]});
u.s-=u.rt->val.fi;
if(u.rt->ls) {
Pair w=u.rt->ls->val;
que.push({u.s+w.fi,u.rt->ls});
}
if(u.rt->rs) {
Pair w=u.rt->rs->val;
que.push({u.s+w.fi,u.rt->rs});
}
}
printf("%d
",ans);
}
int main(){
n=rd(),m=rd(),scanf("%lf",&E);
rep(i,1,m){
int u=rd(),v=rd();db w; scanf("%lf",&w);
AddEdge(v,u,w);
}
Dijkstra(n);
Construct();
Kth_Path();
}