結果

問題 No.807 umg tours
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:24:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,231 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 188,176 KB
最終ジャッジ日時 2025-05-14 13:25:36
合計ジャッジ時間 8,941 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import sys

# Fast I/O
def get_ints(): return map(int, sys.stdin.readline().split())
def get_int(): return int(sys.stdin.readline())

def solve():
    N, M = get_ints()
    
    adj = [[] for _ in range(N)]
    edges = [] # To iterate over all edges later
    for _ in range(M):
        u, v, c = get_ints()
        u -= 1 # 0-indexed
        v -= 1 # 0-indexed
        adj[u].append((v, c))
        adj[v].append((u, c))
        edges.append((u, v, c)) # Store original edge info

    # Dijkstra function
    def dijkstra(start_node):
        distances = [float('inf')] * N
        distances[start_node] = 0
        pq = [(0, start_node)]  # (distance, node)

        while pq:
            d, u_curr = heapq.heappop(pq)

            if d > distances[u_curr]:
                continue

            for v_neighbor, weight in adj[u_curr]:
                if distances[u_curr] + weight < distances[v_neighbor]:
                    distances[v_neighbor] = distances[u_curr] + weight
                    heapq.heappush(pq, (distances[v_neighbor], v_neighbor))
        return distances

    # Calculate shortest distances from spot 1 (node 0)
    dist_from_1 = dijkstra(0)

    output_results = []

    for i in range(N):  # Current target spot is i
        # Base case: tour for spot 1 (node 0)
        if i == 0:
            output_results.append(0)
            continue

        # Shortest distances from current target spot i
        dist_from_i = dijkstra(i)
        
        # Cost without using the ticket
        # Path: 1 -> i -> 1. Total dist: dist_from_1[i] + dist_from_i[0]
        # Since dist_from_i[0] (dist i to 1) == dist_from_1[i] (dist 1 to i)
        min_tour_dist_for_i = 2 * dist_from_1[i]
        if min_tour_dist_for_i == float('inf'): # Should not happen based on problem statement (connected graph)
             min_tour_dist_for_i = float('inf')


        # Iterate over all M original edges to consider making one traversal free
        for u_edge, v_edge, _ in edges: # w_edge (original weight) is not directly used here as it becomes 0
            # Option A: Ticket used on 1 -> i leg
            # Path 1: 1 -> u_edge --0--> v_edge -> i -> 1
            # Cost: dist_from_1[u_edge] + 0 (free) + dist_from_i[v_edge] + dist_from_1[i] (as dist_from_i[0])
            if dist_from_1[u_edge] != float('inf') and \
               dist_from_i[v_edge] != float('inf') and \
               dist_from_1[i] != float('inf'):
                cost1 = dist_from_1[u_edge] + dist_from_i[v_edge] + dist_from_1[i]
                min_tour_dist_for_i = min(min_tour_dist_for_i, cost1)

            # Path 2: 1 -> v_edge --0--> u_edge -> i -> 1 (traversing edge other way)
            # Cost: dist_from_1[v_edge] + 0 (free) + dist_from_i[u_edge] + dist_from_1[i]
            if dist_from_1[v_edge] != float('inf') and \
               dist_from_i[u_edge] != float('inf') and \
               dist_from_1[i] != float('inf'):
                cost2 = dist_from_1[v_edge] + dist_from_i[u_edge] + dist_from_1[i]
                min_tour_dist_for_i = min(min_tour_dist_for_i, cost2)
            
            # Option B: Ticket used on i -> 1 leg
            # Path 3: 1 -> i -> u_edge --0--> v_edge -> 1
            # Cost: dist_from_1[i] + dist_from_i[u_edge] + 0 (free) + dist_from_1[v_edge]
            if dist_from_1[i] != float('inf') and \
               dist_from_i[u_edge] != float('inf') and \
               dist_from_1[v_edge] != float('inf'):
                cost3 = dist_from_1[i] + dist_from_i[u_edge] + dist_from_1[v_edge]
                min_tour_dist_for_i = min(min_tour_dist_for_i, cost3)

            # Path 4: 1 -> i -> v_edge --0--> u_edge -> 1
            # Cost: dist_from_1[i] + dist_from_i[v_edge] + 0 (free) + dist_from_1[u_edge]
            if dist_from_1[i] != float('inf') and \
               dist_from_i[v_edge] != float('inf') and \
               dist_from_1[u_edge] != float('inf'):
                cost4 = dist_from_1[i] + dist_from_i[v_edge] + dist_from_1[u_edge]
                min_tour_dist_for_i = min(min_tour_dist_for_i, cost4)
            
        output_results.append(min_tour_dist_for_i)

    # Print all results
    for res in output_results:
        print(res)

solve()
0