結果

問題 No.1814 Uribo Road (Easy)
ユーザー lam6er
提出日時 2025-03-20 20:21:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 301 ms / 2,000 ms
コード長 2,656 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 85,824 KB
最終ジャッジ日時 2025-03-20 20:23:07
合計ジャッジ時間 6,521 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import permutations

def main():
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx]); idx +=1
    m = int(input[idx]); idx +=1
    k = int(input[idx]); idx +=1

    r_list = list(map(int, input[idx:idx+k]))
    idx +=k

    roads = [ (0,0,0) ]  # dummy for 0 index, roads[1] is road 1

    for i in range(m):
        a = int(input[idx]); idx +=1
        b = int(input[idx]); idx +=1
        c = int(input[idx]); idx +=1
        roads.append( (a, b, c) )

    # Initialize Floyd-Warshall
    INF = float('inf')
    dist = [ [INF] * (n+1) for _ in range(n+1) ]
    for i in range(1, n+1):
        dist[i][i] = 0

    # Update adjacency matrix with roads
    for road in roads[1:]:
        a, b, c = road
        if c < dist[a][b]:
            dist[a][b] = c
            dist[b][a] = c

    # Floyd-Warshall algorithm to find all pairs shortest paths
    for k_via in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if dist[i][j] > dist[i][k_via] + dist[k_via][j]:
                    dist[i][j] = dist[i][k_via] + dist[k_via][j]

    min_total = INF

    # Prepare list of roads to consider
    required_roads = []
    for r in r_list:
        required_roads.append( roads[r] )

    # Generate all permutations of the required roads
    for perm in permutations(required_roads):
        current_dp = {1: 0}  # current positions and their costs

        for step in range(k):
            a, b, c = perm[step]
            next_dp = {}
            for s in current_dp:
                current_cost = current_dp[s]
                # Move to a then take the road to b
                cost_a = current_cost + dist[s][a] + c
                if b in next_dp:
                    next_dp[b] = min(next_dp[b], cost_a)
                else:
                    next_dp[b] = cost_a
                # Move to b then take the road to a
                cost_b = current_cost + dist[s][b] + c
                if a in next_dp:
                    next_dp[a] = min(next_dp[a], cost_b)
                else:
                    next_dp[a] = cost_b
            current_dp = next_dp
            if not current_dp:
                break  # invalid permutation, can't proceed

        if current_dp:
            # After all steps, move to N
            current_min = INF
            for pos in current_dp:
                total = current_dp[pos] + dist[pos][n]
                current_min = min(current_min, total)
            if current_min < min_total:
                min_total = current_min

    print(min_total if min_total != INF else -1)

if __name__ == '__main__':
    main()
0