[CF1842D] Tenzing and His Animal Friends

首先以 $m$ 条 special restrictions 为边建一幅无向图，对于某一分钟的选取方案，我们定义关键边为两侧的点一个被选中，另一个未被选中的边。

然后考察任意一条 $1\to n$ 的路径，不难发现，点 $1$ 总需要被选取，点 $n$ 不可以被选取，因此任何一种选取朋友的方案的任意一刻，这条路径上至少有一条关键边。而在一种游戏方案中，每一条边为关键边的时间不超过它的边权。于是游戏时长不可能超过 $1\to n$ 的任意一条路径的长度，也就不可能超过 $1\to n$ 的最短路。

证明了游戏时长存在一个上界，现在需要构造一种方案使得游戏时长能够达到这个上界。记 $d_i$ 为 $1\to i$ 的最短路，点 $i$ 在 $[1,d_i)$ 这个时间段不被选取，在 $[d_i,d_n]$ 的时间段被选取，于是任意一条边权为 $w$ 的边 $(u,v)$ 满足 $|d_u-d_v|\le w$（最短路的性质），而前者即这条边作为关键边的时长，从而保证了题目的 special restrictions 成立。

然后就可以如此构造答案。