AtCoder Beginner Contest 183 C問題

Python AtCoder

C問題

atcoder.jp

問題（灰色）

N個の都市があります。都市 iから都市 jへ移動するには Ti,jの時間がかかります。都市 1を出発し、全ての都市をちょうど 1度ずつ訪問してから都市 1に戻るような経路のうち、移動時間の合計がちょうど Kになるようなものはいくつありますか？

条件に2≤N≤8と書かれていたので、for文で二重ループをしても問題なしと判断しまして、泥臭く解きました。久しぶりの競プロなので、解法自体はすぐに出てきたのですが、実装に少し時間がかかってしまいました。

ポイントは始点1→終点1なので途中に通過する都市の組み合わせを列挙させた事ですかね。

import itertools
n, k = map(int,input().split())
t = list(map(lambda x: list(map(int, input().split())), range(n)))
 
# 1から1を全て列挙
p = itertools.permutations(range(2,n+1), n-1)
time = []
for lis in p:
  lis = list(lis)
  lis.append(1)
  lis.insert(0,1)
  time.append(sum([t[lis[i-1]-1][lis[i]-1] for i,x in enumerate(lis)]))
print(time.count(k))