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’)$，容易$\text{Dijkstra}$求得$t$的单源最短路$dis_i$，并且建立一棵最短路树

考虑$s\rightarrow 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.在当前递归栈中移动$p\leftarrow p+1$，改变$d$

2-2.模拟上面，建立新的递归栈，同时令指针为$0$

得到$u’=v_{u,p},d’=d+w’_{v,0},p’=0$

如果暴力处理出$S_u$，则预处理复杂度为$O(nm\log m)$，状态扩展复杂度为$O(2k\log k)$

用可持久化可并堆处理$S_u$，$p$记录当前堆顶节点指针

每次扩展$p\leftarrow lson_p$或者$p\leftarrow rson_p$，增加一个扩展状态

则预处理复杂度以及空间复杂度为$O(m\log m)$，状态扩展复杂度为$O(3k\log k)$

Luogu P2483

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#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\n",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();
}