結果

問題 No.8078 Very Simple Traveling Salesman Problem
コンテスト
ユーザー aram14
提出日時 2021-04-01 20:30:20
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,649 bytes
コンパイル時間 112 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 31,424 KB
最終ジャッジ日時 2024-12-20 01:42:31
合計ジャッジ時間 21,938 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

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