結果

問題 No.1812 Uribo Road
コンテスト
ユーザー 梅越
提出日時 2025-08-12 17:35:41
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,528 bytes
コンパイル時間 1,075 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2025-08-12 17:35:46
合計ジャッジ時間 3,125 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq
from math import inf

INF = 10**18

class EOFException(Exception):
    pass

def main():
    tokens = []
    while True:
        try:
            line = sys.stdin.readline()
            if not line:
                raise EOFException()
            tokens.extend(line.split())
        except EOFException:
            break
        
        try:
            idx = 0
            while True:
                N = int(tokens[idx])
                M = int(tokens[idx+1])
                K = int(tokens[idx+2])
                idx += 3
                
                R = []
                for _ in range(K):
                    R.append(int(tokens[idx]) - 1)
                    idx += 1
                
                A, B, C = [], [], []
                for _ in range(M):
                    A.append(int(tokens[idx]) - 1)
                    B.append(int(tokens[idx+1]) - 1)
                    C.append(int(tokens[idx+2]))
                    idx += 3
                
                # Build graph
                G = [[] for _ in range(N)]
                for i in range(M):
                    G[A[i]].append(i)
                    G[B[i]].append(i)
                
                # Special nodes
                ss = []
                for k in range(K):
                    ss.append(A[R[k]])
                    ss.append(B[R[k]])
                ss.append(0)
                ss.append(N-1)
                
                # Dijkstra from each special node
                dist = [[INF] * N for _ in range(2*K+2)]
                for x in range(2*K + 2):
                    dist[x][ss[x]] = 0
                    heap = [(0, ss[x])]
                    while heap:
                        c, u = heapq.heappop(heap)
                        if c > dist[x][u]:
                            continue
                        for i in G[u]:
                            v = A[i] ^ B[i] ^ u
                            cc = c + C[i]
                            if cc < dist[x][v]:
                                dist[x][v] = cc
                                heapq.heappush(heap, (cc, v))
                
                # DP setup
                dp = [[INF] * (2*K + 2) for _ in range(1 << K)]
                dp[0][2*K] = 0  # Starting from node 0 (2*K-th in ss)
                
                for p in range(1 << K):
                    for x in range(2*K + 2):
                        if dp[p][x] == INF:
                            continue
                        for k in range(K):
                            if not (p >> k) & 1:
                                # Try both directions of the k-th required edge
                                new_p = p | (1 << k)
                                # Case 1: A -> B
                                cost1 = dp[p][x] + dist[x][A[R[k]]] + C[R[k]]
                                if cost1 < dp[new_p][2*k + 1]:
                                    dp[new_p][2*k + 1] = cost1
                                # Case 2: B -> A
                                cost2 = dp[p][x] + dist[x][B[R[k]]] + C[R[k]]
                                if cost2 < dp[new_p][2*k]:
                                    dp[new_p][2*k] = cost2
                
                # Find the minimal answer
                ans = INF
                for x in range(2*K + 2):
                    ans = min(ans, dp[(1 << K) - 1][x] + dist[x][N-1])
                print(ans)
                
        except IndexError:
            break

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