Problem p02871 (python)

Fixed submission:
def warshall_floid(graph):
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|N|^3)
    """
    n = len(graph)
    INF = 10**18
    dp = [[INF]*n for i in range(n)]
    for i in range(n):
        dp[i][i] = 0

    for i in range(n):
        for j, cost in graph[i]:
            dp[i][j] = cost
            dp[j][i] = cost

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


def trace_route(start, goal):
    """warshall-floid法で求めた最短距離を通るための経路を復元する
    計算量: O(|N|^2)
    """
    pos = start
    ans = []
    while pos != goal:
        ans.append(pos)
        for next_pos in range(n):
            if next_pos != pos and dp[pos][next_pos] + dp[next_pos][goal] == dp[pos][goal]:
                pos = next_pos
                break
    ans.append(goal)
    return ans


# 値を入力する
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
t_max = int(input())
query = [None] * t_max
for i in range(t_max):
    tmp = int(input())
    query[i] = [list(map(int, input().split())) for i in range(tmp)]

# グラフを構築
graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

# 最短距離を求める
dp = warshall_floid(graph)

visited = [False] * n
visited[0] = True
route = [0]
pos = 0
total_cost = 0
while True:
    kyori = 10**9
    next_pos = -1
    for next_p, cost in enumerate(dp[pos]):
        if visited[next_p]:
            continue
        if cost< kyori:
            kyori = cost
            next_pos = next_p
    if next_pos == -1:
        break
    else:
        visited[next_pos] = True
        route.append(next_pos)
        total_cost += kyori

for i in range(n-1):
    pos = route[i]
    next_pos = route[i+1]

for i in range(t_max):
	print(-1)

Buggy submission (verdict: Runtime Error):
import random
import time
s_time = time.time()
NAPIER = 2.71828182846
INF = 10**18


def warshall_floid(graph):
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(N^3)
    """
    dp = [[INF]*n for i in range(n)]
    next_ = [[-1]*n for i in range(n)]
    for i in range(n):
        dp[i][i] = 0

    for i in range(n):
        for j, cost in graph[i]:
            dp[i][j] = cost
            dp[j][i] = cost

    for i in range(n):
        for j in range(n):
            next_[i][j] = j

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
                    next_[i][j] = next_[i][k]
    return dp, next_


def trace_route(start, goal):
    """warshall-floid法で求めた最短距離を通るための経路を復元する
    計算量: O(N)
    """
    pos = start
    res = []
    while pos != goal:
        res.append(pos)
        pos = next_[pos][goal]
    res.append(goal)
    return res


def tsp(use_v: set):
    """Nearest Neighbourからの焼きなまし2optで地点0から地点0へ巡回する順番を決める
    例) route: 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> 0 のとき
    route = [0, 3, 2, 5, 4, 1, 0]
    """
    
    # 初期値のrouteをNearest Neighbourで決める
    visited = [False if i in use_v else True for i in range(n)]
    visited[0] = True
    if len(use_v) / n > 0.8:
        visited = [False] * n
        visited[0] = True

    route = [0]
    pos = 0
    total_cost = 0
    while True:
        kyori = 10**9
        next_pos = -1
        for next_p, cost in enumerate(dp[pos]):
            if visited[next_p]:
                continue
            if cost < kyori:
                kyori = cost
                next_pos = next_p
        if next_pos == -1:
            break
        else:
            visited[next_pos] = True
            route.append(next_pos)
            pos = next_pos
            total_cost += kyori
    total_cost += dp[0][route[-1]]
    route.append(0)
    route_n = len(route) - 1

    # 最も良いrouteを焼きなまし法で決める
    if route_n == n:
        T = 1000000
        cool = 0.999995
        cnt = 0
        best_score = total_cost
        best_route = route[0:]
        score = total_cost

    #else:
    #    T = 100000000
    #    cool = 0.9
    #    cnt = 0
    #    best_score = total_cost
    #    best_route = route[0:]
    #    score = total_cost

    while cnt < 7000000:
        cnt += 1
        #スワップする点を選択
        ind1 = random.randrange(0, route_n)
        ind2 = random.randrange(0, route_n)
        while True:
            if ind1 == ind2:
                ind2 = random.randrange(0, route_n)
            else:
                break
        if ind1 > ind2:
            ind1, ind2 = ind2, ind1
        
        # スワップする前のコスト
        before_cost = dp[ route[ind1] ][ route[ind1+1] ] + dp[ route[ind2] ][ route[ind2+1] ]
        # スワップした後のコスト
        after_cost = dp[ route[ind1] ][ route[ind2] ] + dp[ route[ind1+1] ][ route[ind2+1] ] 
        # 温度から確率を定義
        p = pow(NAPIER, -abs(before_cost - after_cost) / T)
        # 遷移
        if (after_cost < before_cost or random.random() < p):
            route = route[0:ind1+1] + route[ind1+1:ind2+1][::-1] + route[ind2+1:]
            score = score + after_cost - before_cost
        # ベストスコアを保存しておく
        if score < best_score:
            best_score = score
            best_route = route[0:]
        # 温度を下げる
        T = T * cool
 
        #状態を確認する
        #if cnt % 100000 == 1:
        #    print(cnt, p)

    return best_route, best_score


def strict_tsp(use_v: set):
    """巡回セールスマン問題の厳密解を解く"""
    n_tsp = len(use_v)
    list_tsp = sorted(list(use_v))

    dq = [[INF]*n_tsp for i in range(1 << n_tsp)]
    dq[1 << 0][0] = 0

    next_tsp = [[0]*n_tsp for i in range(1 << n_tsp)]
    for bit_state in range(1 << n_tsp):
        for j in range(n_tsp):
            next_tsp[bit_state][j] = -1

    for bit_state in range(1 << n_tsp):
        for i in range(n_tsp):
            # bit_stateにiが含まれてない場合は飛ばす
            if not (bit_state >> i) & 1:
                continue
            for j in range(n_tsp):
                # bit_stateにjが含まれている場合は飛ばす
                if ((bit_state >> j) & 1):
                    continue
                if dq[bit_state|(1 << j)][j] > dq[bit_state][i] + dp[list_tsp[i]][list_tsp[j]]:
                    dq[bit_state|(1 << j)][j] = dq[bit_state][i] + dp[list_tsp[i]][list_tsp[j]]
                    next_tsp[bit_state|(1 << j)][j] = i

    min_cost = INF
    last_pos = -1
    for i in range(0, n_tsp)[::-1]:
        if dq[(1 << n_tsp) - 1][i] + dp[0][list_tsp[i]] < min_cost:
            min_cost = dq[(1 << n_tsp) - 1][i] + dp[0][list_tsp[i]] 
            last_pos = i

    pos = 0
    res = [0, list_tsp[last_pos]]
    bit_state = (1 << n_tsp) - 1
    while True:
        res.append(list_tsp[next_tsp[bit_state][last_pos]])
        tmp = bit_state
        bit_state -= (1 << last_pos)
        last_pos = next_tsp[tmp][last_pos]
        if res[-1] == 0:
            break

    return res, min_cost


# 値を入力する
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
t_max = int(input())
query = [None] * t_max
for i in range(t_max):
    tmp = int(input())
    if tmp == 0:
        continue
    else:
        query[i] = list(map(int, input().split()))

# グラフを構築
graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

# 最短距離を求める
dp, next_ = warshall_floid(graph)

#全部通るときの最短ルート
tmp_set = set([i for i in range(n)])
all_route, all_cost = tsp(tmp_set)


start_ti = 1
prev_start_ti = 0
tmp_set = set([0])
ans = []
flag = True
while flag:
    for i in range(prev_start_ti, start_ti):
        if t_max <= i:
            flag = False
            break
        if query[i] is None:
            continue
        tmp_set.add(query[i][1] - 1)

    # 荷物が何も無い時
    if len(tmp_set) == 1:
        ans.append(-1)
        start_ti += 1
        prev_start_ti = start_ti - 1
        continue
    # 配達箇所が20個以下の時 -> 厳密解を解く    
    elif len(tmp_set) <= 20:
        route, cost = strict_tsp(tmp_set)
    # それ以外 -> 焼きなまし法   
    else:
        route, cost = tsp(tmp_set)

    for i in range(len(route) - 1):
        pos = route[i]
        next_pos = route[i+1]
        tmp = trace_route(pos, next_pos)
        for j in range(len(tmp)-1):
            for _ in range(dp[tmp[j]][tmp[j+1]]):
                ans.append(tmp[j+1] + 1)

    start_ti += cost
    prev_start_ti = start_ti - cost

for i in ans[0:t_max]:
    print(i)

Buggy submission (verdict: Runtime Error):
import random
import time
s_time = time.time()
NAPIER = 2.71828182846
INF = 10**18


def warshall_floid(graph):
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(N^3)
    """
    dp = [[INF]*n for i in range(n)]
    next_ = [[-1]*n for i in range(n)]
    for i in range(n):
        dp[i][i] = 0

    for i in range(n):
        for j, cost in graph[i]:
            dp[i][j] = cost
            dp[j][i] = cost

    for i in range(n):
        for j in range(n):
            next_[i][j] = j

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
                    next_[i][j] = next_[i][k]
    return dp, next_


def trace_route(start, goal):
    """warshall-floid法で求めた最短距離を通るための経路を復元する
    計算量: O(N)
    """
    pos = start
    res = []
    while pos != goal:
        res.append(pos)
        pos = next_[pos][goal]
    res.append(goal)
    return res

    
# 値を入力する
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
t_max = int(input())
#query = [None] * t_max
#for i in range(t_max):
#    tmp = int(input())
#    query[i] = [list(map(int, input().split())) for i in range(tmp)]

# グラフを構築
graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))


# 最短距離を求める
dp, next_ = warshall_floid(graph)

def tsp():
    """Nearest Neighbourからの焼きなまし2optで地点0から地点0へ巡回する順番を決める
    例) route: 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> 0 のとき
    route = [0, 3, 2] + [0] + [5, 4, 1, 0]
    """
    
    # 初期値のrouteをNearest Neighbourで決める
    visited = [False] * n
    visited[0] = True
    route = [0]
    pos = 0
    total_cost = 0
    while True:
        kyori = 10**9
        next_pos = -1
        for next_p, cost in enumerate(dp[pos]):
            if visited[next_p]:
                continue
            if cost < kyori:
                kyori = cost
                next_pos = next_p
        if next_pos == -1:
            break
        else:
            visited[next_pos] = True
            route.append(next_pos)
            pos = next_pos
            total_cost += kyori
    total_cost += dp[0][route[-1]]
    route.append(0)

    route = route[0:len(route)//2] + [0] + route[len(route)//2:]

    # 最も良いrouteを焼きなまし法で決める
    T = 100000
    cool = 0.99995
    cnt = 0
    best_score = total_cost
    best_route = route[0:]
    score = total_cost

    while cnt < 1000000:
        cnt += 1
        #スワップする点を選択
        ind1 = random.randrange(0, n+1)
        if ind1 < len(route)//2:
            ind2 = random.randrange(0, len(route)//2)
        elif len(route)//2 <= ind1:
            ind2 = random.randrange(len(route)//2, n+1)
        else:
            continue
            
        ind3 = ind1
        if ind1 < len(route)//2:
            ind4 = (len(route)//2 - ind1) + len(route)//2 - 1
        else:
            ind4 = len(route)//2 - (ind1 - len(route)//2) - 1
        if ind1 > ind2:
            ind1, ind2 = ind2, ind1
        
        # スワップする前のコスト
        before_cost = dp[ route[ind1] ][ route[ind1+1] ] + dp[ route[ind2] ][ route[ind2+1] ]
        # スワップした後のコスト
        after_cost = dp[ route[ind1] ][ route[ind2] ] + dp[ route[ind1+1] ][ route[ind2+1] ] 
        # 温度から確率を定義
        p = pow(NAPIER, -abs(before_cost - after_cost) / T)
        # 遷移
        if (after_cost < before_cost or random.random() < p):
            route = route[0:ind1+1] + route[ind1+1:ind2+1][::-1] + route[ind2+1:]
            score = score + after_cost - before_cost
        # ベストスコアを保存しておく
        if score < best_score:
            best_score = score
            best_route = route[0:]

        ind1 = ind3
        ind2 = ind4
        if ind1 > ind2:
            ind1, ind2 = ind2, ind1
        # スワップする前のコスト
        before_cost = dp[ route[ind1] ][ route[ind1+1] ] + dp[ route[ind2] ][ route[ind2+1] ]
        # スワップした後のコスト
        after_cost = dp[ route[ind1] ][ route[ind2] ] + dp[ route[ind1+1] ][ route[ind2+1] ] 
        # 温度から確率を定義
        p = pow(NAPIER, -abs(before_cost - after_cost) / T)
        # 遷移
        if (after_cost < before_cost or random.random() < p):
            route = route[0:ind1+1] + route[ind1+1:ind2+1][::-1] + route[ind2+1:]
            score = score + after_cost - before_cost
        # ベストスコアを保存しておく
        if score < best_score:
            best_score = score
            best_route = route[0:]
            
        # 温度を下げる
        T = T * cool
 
        #if cnt % 100000 == 1:
        #    print(cnt, p)
    return best_route


route = tsp()
#print(route)
# ans: スタートから全部の頂点を通ってスタートに帰るときのコマンド
ans = []
for i in range(n):
    pos = route[i]
    next_pos = route[i+1]
    tmp = trace_route(pos, next_pos)
    for j in range(len(tmp)-1):
        for _ in range(dp[tmp[j]][tmp[j+1]]):
            ans.append(tmp[j+1] + 1)

#path_w = './output.txt'
#f =  open(path_w, mode='w')
times = (t_max - 500) // len(ans)
nokori = (t_max - 500) - times * len(ans)

for _ in range(nokori):
    print(-1)
cnt = nokori
while True:
    for i in ans:
        cnt += 1
        print(i)
        #f.write(str(i) + "\n")
        if cnt == t_max:
            break
    else:
        continue
    break