AtCoder ABC 021 B – 嘘つきの高橋くん Python解説

スポンサーリンク

嘘つきの高橋くん

あなたと高橋君は、AtCoder 王国に住んでいます。AtCoder 王国には、N 個の町と、町同士を結ぶ何本かの道路が存在し、道路は双方向に移動可能です。 N 個の町はそれぞれ 町 1,町 2,…町 N と呼ばれています。

高橋君はあなたの家に遊びに行くことにしました。そして、高橋君は町 a から出発して、ちょうど K 回 AtCoder 王国のどこかの町を経由して町 b にあるあなたの家に到着しました。

高橋君は町 a から町 b まで最短経路で移動してきたと主張していますが、あなたには彼が嘘をついているよう思えます。 しかし、あなたは具体的に町同士を結ぶ道路がどのような構成になっているか全く知らないため、高橋君が辿った経路が本当に最短経路なのかどうか判定できません。

あなたは高橋君がどの順番で町を経由したかを聞き出すことに成功しました。ただし、この情報には出発/到着地点である町 a と町 b が含まれません。

あなたはこの情報を元に、高橋君が最短経路で移動していた可能性があるかどうかを出力するプログラムを書くことにしました。 町 a から町 b への最短経路とは、町 a から町 b への移動経路において道路を通る回数が最小となるような経路のことを言います。

高橋君が辿った経路が最短経路となるような町と道路の構成が 1 つでも存在する場合、最短経路で移動した可能性があると言えます。一方、そのような構成がない場合、その可能性は無いと言えます。

AtCoder Beginner Contest 021「嘘つきの高橋くん」

高橋君が最短経路で移動していた可能性があるかどうかを出力する。なんだか面倒な気もしますが、この問題でいう最短経路は重複した町の番号がなければ大丈夫なのでsetを使って解いていきましょう。

n = int(input())
a, b = map(int, input().split())
k = int(input())
p = list(map(int, input().split()))
 
town = [a] + [b] + p
 
if len(town) == len(set(town)):
    print("YES")
else:
    print("NO")

出発する町の番号a、到着する町の番号b、経由する町の番号pがを受け取ったら変数townに加えます。続くif文でtownの配列の要素数と、setで重複した要素を削除したあとの要素数を比べ、要素数が同じなら最短経路を通った可能性があるのでYES、要素数が違えば同じ町を通っているのでNOになります。