第k小路径



给定一张n个点 m 条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第k小的路径。保证存在至少 k条路径，上述参数满足1<=n,m<=10^5 和1<=k<=10^18表示。

在程序中，我们求出从每个点出发的路径数量。超过10^18的数都用 10^18表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。



试补全程序。

#include <iostream>


#include <algorithm>


#include <vector>





const int MAXN = 100000;


const long long LIM =1000000000000000000ll;





int n,m,deg[MAXN];


std::vector<int> E[MAXN];


long long k, f[MAXN];





int next(std::vector<int> cand, long long &k) {


	std::sort(cand.begin(), cand.end());


	for (int u : cand) {


		if ( __(1)__ ) return u;


			k -= f[u];


	}


	return -1;


}





int main() {


	std::cin >>n>> m >> k;


	for (int i=0;i<m; ++i){


		int u, v;


		std::cin >> u>> v;


		E[u].push_back(v);


		++deg[v];


		}


	std::vector<int> Q;


	for (int i= 0;i<n; ++i)


		if (!deg[i]) Q.push_back(i);


	for (int i=0;i<n;++i){


		int u= Q[i];


		for (int v :E[u]){


			if (  __(2)__ ) Q.push_back(v);


			--deg[v];


		}


	}


		std::reverse(Q.begin(), Q.end());


	for (int u:Q){


		f[u] = 1;


		for (int v : E[u]) f[u] = __(3)__ ;		 


	}


	int u= next(Q,k);


	std::cout << u << std::endl;


	while ( __(4)__ ) {


		__(5)__ ;


		u= next(E[u], k);


		std::cout << u << std::end1;


	}


	return 0;


}

选择题