結果

問題 No.3078 Very Simple Traveling Salesman Problem
ユーザー aram14aram14
提出日時 2021-04-01 20:34:06
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,649 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 89,216 KB
最終ジャッジ日時 2024-05-10 06:42:53
合計ジャッジ時間 3,884 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
59,392 KB
testcase_01 AC 45 ms
54,144 KB
testcase_02 AC 45 ms
54,144 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, namedtuple

def connect(graph, u, v, w):
    graph[u][v] = w
    graph[v][u] = w

def tsp(d):
    """solve the traveling salesman problem by bitDP
    Parameters
    -----------
    d : list of list or numpy.array
        distance matrix; d[i][j] is the distance between i and j
    Returns
    -------
    the minimum cost of TSP
    """
    n = len(d)  # number of cities

    # DP[A] = {v: value}
    #   A is the set of visited cities other than v
    #   v is the last visited city
    #   value is the cost
    DP = defaultdict(dict)

    for A in range(1, 1 << n):
        if A & 1 << 0 == 0: # 0 is not included in set A
            continue

        # main
        for v in range(n):
            if A & (1 << v) == 0:  # v is not included in set A
                if A == (1 << 0):  # v is the first visited city
                    DP[A][v] = d[0][v] if d[0][v] > 0 else float('inf')
                else:
                    # A ^ (1 << u) <=> A - {u}
                    DP[A][v] = float('inf')
                    for u in range(1, n):
                        if d[u][v] > 0 and A & (1 << u) != 0:
                            DP[A][v] = min(DP[A][v], DP[A ^ (1 << u)][u] + d[u][v])
    V = 1 << n
    DP[V][0] = float('inf')
    for u in range(1, n):
        if d[u][0] > 0 and A & (1 << u) != 0:
            DP[V][0] = min(DP[V][0], DP[A ^ (1 <<u)][u] + d[u][0])

    return DP[V][0]

# 入力
N, M = map(int, input().split())
graph = [[0 for i in range(N)] for j in range(N)]
for _ in range(M):
    u, v, w = map(int, input().split())
    connect(graph, u-1, v-1, w)

res = tsp(graph)
print(res)
0