【競プロ典型90問】「032 - AtCoder Ekiden(★3)」解法
Free-PhotosによるPixabayからの画像

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。

問題

032 - AtCoder Ekiden(★3)

ポイント

10人の選手の並べ方の総数は10! = 3628800通りです。
総当りで調べても十分時間内に間に合うので、噂になっている2人が並ばない組み合わせを全探索します。

pythonで並べ方の総数を全探索する際はitertools.permutationsを使うと便利です。

以上を踏まえ、実装したコードがこちらです。
尚、PythonだとTLEとなるためPyPyで提出しました。

コード

"""
10!が十分小さな値なので、全探索できる
険悪な関係をリストで所持しておき、全探索する際にチェックする
"""

def main():
    import sys
    import itertools
    sys.setrecursionlimit(10 ** 9)
    input = sys.stdin.readline

    N = int(input())
    A = [list(map(int, input().split(" "))) for _ in range(N)]  # 各々の走る速さのリスト
    M = int(input())
    R = [[0 for _ in range(N)] for _ in range(N)]  # 噂のリスト

    # 不仲な噂を取得
    for _ in range(M):
        x, y = map(int, input().split(" "))
        R[x-1][y-1] = R[y-1][x-1] = 1  # 不仲を1とする

    ans = 10 ** 9
    for p in list(itertools.permutations(range(N))):
        tmp = 0
        for i in range(len(p)):
            tmp += A[p[i]][i]  # p[i]番の選手が[i]番目の区画を走る時の速さ
            if i < len(p)-1 and R[p[i]][p[i+1]] == 1:  # 噂のチェック ※i < len(p) - 1 の条件を入れ忘れると index out of rangeとなるので注意
                break
        else:
            if tmp < ans:
                ans = tmp

    print(ans if ans != 10 ** 9 else -1)


if __name__ == '__main__':
    main()

おすすめの記事