P9829 [ICPC 2020 Shanghai R] Traveling Merchant

题目描述

劳伦斯先生是一位在不同城市转售商品的旅行商人。基本地,为了赚钱,他需要以低价买进商品,再以高价卖出。现在请你为他规划一条可以一直盈利的旅行路线。 简单地说,假设有 $n$ 座城市,标号为 $0$ 到 $n-1$ ,以及 $m$ 条连接特定两座城市的路,劳伦斯先生可以通过这些路到访每座城市。最初劳伦斯先生位于第 $0$ 座城市,并且对于城市 $i$ 都有一个起始价格 $c_i$ 。根据市场规律,当他从城市 $i$ 来到相邻的城市 $j$ 时(当且仅当城市 $i$ 与城市 $j$ 之间有路径相连时,才称 $i$ 与 $j$ 为相邻城市),城市 $i$ 的价格状况会发生变化(高价会变成低价,低价也可能变成高价)。而因为一些原因(比如商品的新鲜程度,旅行费用,税务等),他**必须**: - 从城市 $0$ 出发并在城市 $0$ 购买一些商品。保证城市 $0$ 的起始价格很**低**。 - 每当他到达一座城市后,他**必须**售卖**或**购买一些商品。 - 若他在城市 $i$ 购买了商品,他就必须去一座与 $i$ 相邻且价格 $c_j$ **高于** $c_i$ 的城市 $j$ ,并在那里卖掉手中来自城市 $i$ 的商品。 - 若他在城市 $i$ 售卖了商品,他就必须去一座与 $i$ 相邻且价格 $c_j$ **低于** $c_i$ 的城市 $j$,并在那里购买一些商品。 因此,最终路径会始终重复 ``低价购入`` 和 ``高价卖出`` 。 一条无尽的盈利路线由无尽的城市序列 $p_0,p_1 \dots$ 组成。其中,城市 $p_i$ 与城市 $p_{p+1}$ 之间有路径相连,$p_0 = 0$,且价格高低是交替循环的,也就是说当 $k \ge 0$ 时,城市 $p_{2k}$ 的价格 $c_{p_{2k}} = \text{Low}$ (要在这个城市购买商品) 而相邻城市 $p_{2k+1}$ 的价格 $c_{p_{2k+1}} = \text{Hign}$ (要在这个城市卖出商品)。 **注意**:$c_{p_i}$ 是 **到达** 城市 $p_i$ 时的价格,而当他第二次到达城市 $p_i$ 时,这个价格可能会因为市场规律而变化。 你需要写一个程序,判断是否有这样一条永远盈利的路径存在。

输入格式

输出格式

说明/提示

In the first sample test case, the endless earning path is $0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow \dots$. In the illustration, cities with $\text{Low}$ price are filled with stripe. ![](https://cdn.luogu.com.cn/upload/image_hosting/2ohq2wfi.png) In the second sample test case, Mr. Lawrence can only make one move from city $0$ and after that all cities will have $\text{High}$ price. Thus, no further moves can be made. ![](https://cdn.luogu.com.cn/upload/image_hosting/fcv1tw87.png)