[伯俊]1389ケビン・ベーコンの6次法則

質問する

ケビン・ベーコンの第6段階の法則によると、地球上の誰もが第6段階でお互いの知っている人に連絡することができる.ケビン・ベーコンゲームは、任意の2人が少なくともいくつかの段階で行うことができるゲームです.
例えば、全く関係ないような仁荷(インハ)大学の李ホホホ氏と西江(ソガン)大学のミン·セヒ氏は、何段階で続けられるだろうか.
千民浩と李浩浩は同じ学校に通っている.千民浩と崔伯俊はBaekjoonオンラインJudgeを通じて知り合った.崔柏俊は金善英とともにスターリングリンクを創設した.金善英と金道は現在、同じ学校のサークルに所属している.金道現と閔世熙は同じ学校に通っていて、知り合いだった.李江浩(イ·ガンホ)、千民浩(チョン·ミンホ)、崔伯俊(チェ·ボジュン)、金善英(キム·ソンヨン)、金道賢(キム·ドヒョン)、閔世煕(ミン·セヒ)のように、5段階だけを経ればいいということだ.
ケビン・ベーコンは、アメリカのハリウッド映画スターたちがケビン・ベーコンゲームを一緒に遊ぶときに現れる段階の総和が最も少ない人だという.
今日BaekjoonオンラインJudgeのプレイヤーの中で、ケビンベーコンの数が一番少ない人を探しています.Kevinベーコンの数は、すべての人とKevinベーコンゲームをしているときに現れる段階の和です.
例えば、BOJのプレイヤーは5名、1と3、1と4、2と3、3と4、4と5が友人であると仮定します.
1は2〜3が2段階、3〜1段階、4〜1段階、5〜4が2段階で分かる.したがって、Kevinベーコンの数は2+1+1+2=6である.
2は、1〜3が2段階、3〜1段階、4〜3が2段階、5〜3及び4が3段階を通過する.したがって、Kevinベーコンの数は2+1+2+3=8である.
3は1から1段階、2から1段階、4から1段階、5から4は2段階しか知らない.したがって、Kevinベーコンの数は1+1+1+2=5である.
4 1から1段階、2から3、2段階、3から1段階、5から1段階でわかります.4のケビンベーコンの数は1+2+1+1=5である.
最後の5は1〜4〜2段階、2〜4及び3は3段階、3〜4は2段階、4〜1段階を通過すれば分かる.5のケビンベーコンの数は2+3+2+1=8です.
5人のプレイヤーの中で、ケビンベーコンの数が最も少ないのは3と4です.
BOJプレイヤーの数と友人関係を入力すると、最も少ないケビンベーコンを探すプログラムを作成してください.

入力

第1行は、ユーザ数N(2≦N≦100)と、親友関係数M(1≦M≦5000)を与える.2行目から、M行には友人関係があります.友人関係はAとBからなり、AとBが友人であることを意味する.AとBが友達なら、BとAも友達で、AとBは同じことはありません.友達関係が繰り返されるかもしれませんが、いない友達は一人もいません.また、誰もが友達の関係でつながっています.人の番号は1からNで、二人は同じ番号を持っていません.

しゅつりょく

1行目の出力BOJプレイヤーの中でケビンベーコンの数が一番小さい人.このような人が複数いれば、出力数が一番小さい人です.

正解

import sys

user, rel = list(map(int, sys.stdin.readline().split()))
INF = 10000000
f = [[INF] * user for _ in range(user)]

for _ in range(rel):
    a, b = list(map(int, sys.stdin.readline().split()))
    f[a - 1][b - 1] = 1
    f[b - 1][a - 1] = 1


for k in range(user):
    for i in range(user):
        for j in range(user):
            if f[i][j] > f[i][k] + f[k][j]:
                f[i][j] = f[i][k] + f[k][j]
sum = INF
kevin = 0
for i, _ in enumerate(f):
    temp = 0
    for a in _:
        temp += a
    if temp < sum:
        sum = temp
        kevin = i + 1
   
print(kevin)

フロイドとシエルのことを覚えたばかりでよく解決した問題だ.フロイドとシエルを使えばすぐに問題を解決できる.