Codeforces Round #436 (Div. 2) F Cities Excursions

题意是给你一个有向图,点n <= 3000, 边m <= 3000,从s到t的路径必须是最小字典序,q<=400000次询问,从s到t中路径第k个点是什么,否则输出-1.

7 7 5
1 2
2 3
1 3
3 4
4 5
5 3
4 6
1 4 2
2 6 1
1 7 3
1 3 2
1 3 5

解释下样例2-6。

2-6的路径为2-3-4-5-3-5-3。。。-5-6无限循环,所以可以当作这个路径不存在,所以为-1

1-3的路径为1-2-3 

如果在线做复杂度肯定要高,把询问的边存储,枚举出发点离线解决

用vector存储路径,肯定每个vector都要sort一下,保证每次走的是最小的

如果没有环,当然很容易做,那么怎么当有环的情况呢?我们会发现,

继续以第二个样例,如果有环,我们可能就不能计算答案了,这时候是无线循环的情况,

所以我们当出环以后才能继续解决查询的问题,那么标记一下环的个数和每个点在环内的个数就好啦

瞎bb了很多,上代码了

http://codeforces.com/contest/864/submission/30743832

原文地址:https://www.cnblogs.com/cshg/p/7597884.html