結果

問題 No.1301 Strange Graph Shortest Path
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:22:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,051 bytes
コンパイル時間 289 ms
コンパイル使用メモリ 81,568 KB
実行使用メモリ 141,596 KB
最終ジャッジ日時 2025-04-16 00:23:55
合計ジャッジ時間 19,230 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq
from collections import defaultdict

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

    edges = []
    adj = [[] for _ in range(N+1)]  # adj[u] contains (v, c, d, edge_idx)
    for i in range(M):
        u = int(input[idx]); idx +=1
        v = int(input[idx]); idx +=1
        c = int(input[idx]); idx +=1
        d = int(input[idx]); idx +=1
        edges.append((u, v, c, d))
        adj[u].append((v, c, d, i))
        adj[v].append((u, c, d, i))

    # First Dijkstra: from 1 to N, using c as cost
    INF = 1 << 60
    dist = [INF] * (N+1)
    dist[1] = 0
    parent = [-1] * (N+1)
    heap = []
    heapq.heappush(heap, (0, 1))

    while heap:
        d_u, u = heapq.heappop(heap)
        if d_u > dist[u]:
            continue
        for (v, c, _, idx_edge) in adj[u]:
            if dist[v] > d_u + c:
                dist[v] = d_u + c
                parent[v] = (u, idx_edge)
                heapq.heappush(heap, (dist[v], v))

    # Reconstruct path from N to 1
    path_edges = set()
    current = N
    while current != 1:
        if parent[current] == -1:
            break  # no path, but problem states the graph is connected
        u, idx_edge = parent[current]
        uu, vv, _, _ = edges[idx_edge]
        if uu > vv:
            uu, vv = vv, uu
        path_edges.add(idx_edge)
        current = u

    # Second Dijkstra: from N to 1, using d for edges in path_edges, else c
    dist2 = [INF] * (N+1)
    dist2[N] = 0
    heap2 = []
    heapq.heappush(heap2, (0, N))

    while heap2:
        d_u, u = heapq.heappop(heap2)
        if d_u > dist2[u]:
            continue
        if u == 1:
            break
        for (v, c, d, idx_edge) in adj[u]:
            cost = d if idx_edge in path_edges else c
            if dist2[v] > d_u + cost:
                dist2[v] = d_u + cost
                heapq.heappush(heap2, (dist2[v], v))

    total = dist[N] + dist2[1]
    print(total)

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