「Codeforces 1138E」Museums Tour
题目链接:Codeforces 1138E
在国家 $N$ 中,有 $n$ 个城市通过 $m$ 条单向道路连接。尽管这个国家看起来并不是那么引人注目,但是这里有两件很有意思的事情。首先,这里的一周有 $d$ 天;另外,每个城市恰好有一个博物馆。
旅行社的员工知道每个博物馆的开放日期,他们正在为游客们制定一项新的旅游计划。旅游从标号为 $1$ 的首都城市出发,并且旅游的第一天必须在某一周的第一天。每天白天,如果当前城市的博物馆开放,那么游客可以进入博物馆参观;否则什么都做不了。晚上,游客要么结束旅游,要么通过道路前往下一个城市。注意,旅游过程中允许重复经过同一个城市。
你需要为旅游制定一条路线,使得在旅游期间参观的不同博物馆数量最多。
数据范围:$1 \le n \le 10 ^ 5$,$0 \le m \le 10 ^ 5$,$1 \le d \le 50$。