(第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中， “路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。
在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序。
01 #include <iostream>
02 #include <algorithm>
03 #include <vector>
04
05 const int MAXN = 100000;
06constlonglongLIM=100000000000000000011;
07
08 int n,m,deg[MAXN];
09 std::vector<int> E[MAXN];
10 long long k,f[MAXN];
11
12 int
next(std::vector<int>cand,long long
&k){
13 std::sort(cand.begin(),cand.end());
14 for(int u : cand){
15 if (①)return u;
16 k -= f[u];
17}
18 return -1;
19}
20
21 int main(){
22std::cin>>n>>m>>k;
23for(inti=0;i<m;++i){
24 int u, v;
25 std::cin >>u >> v;//一条从u到v的边
26 E[u].push_back(v);
27 ++deg[v];
28}
29 std::vector<int> Q;
30for(inti=0;i<n;++i)
31 if (!deg[i])Q.push_back(i);
32for(inti=0;i<n;++i){
33 int u = Q[i];
34 for (int v : E[u]){
35 if (②)Q.push_back(v);
36 --deg[v];
37 }
38}
39 std::reverse(Q.begin(), Q.end());
40 for(int u : Q){
41 f[u]= 1;
42 for(int v:E[u])f[u]=③;
43}
44 int u = next(Q,k);
45 std::cout << u << std::endl;
46while(④){
47 ⑤;
48 u = next(E[u],k);
49 std::cout << u << std::endl;
50}
51 return 0;
52}
①处应填( )
k >= f[u]
k <= f[u]
k >f[u]
k< f[u]
②处应填( )
deg[v]== 1
deg[v]== o
deg[v]>1
deg[v]>o
③处应填( )
std::min(f[u]+ f[v],LIM)
std::min(f[u]+ f[v]+ 1,LIM)
std::min(f[u]* f[v],LIM)
std::min(f[u]*(f[v]+ 1),LIM)
④处应填( )
u!=-1
!E[u].empty()
k >o
k >1
⑤处应填( )
k += f[u]
k -= f[u]
--k
++k