【競技プログラミング】AtCoder Beginner Contest 369_E問題

Posted at 2025-03-08

問題

既存投稿一覧ページへのリンク

一覧ページ

解法手順1

ワーシャルフロイド法で全島間の最短距離を前計算
各クエリに対して、指定された橋を全ての可能な順序で渡る場合を試す
各順序において、橋の渡り方（どちら向きに渡るか）の全パターンを検討
最小の移動時間を求める

1. 入力と前処理

N個の島とM本の橋の情報を読み込む
各橋は島U_iと島V_iを結び、渡るのにT_i時間かかる
Q個のクエリを読み込む（各クエリでは特定のK_i本の橋を渡る必要がある）

2. 全島間の最短距離計算

島間の直接移動時間を初期化（橋がない場合は∞）

ワーシャルフロイド法を使って全ての島のペア間の最短距離を計算

for k in range(num_islands):
    for i in range(num_islands):
        for j in range(num_islands):
            distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

3. 各クエリの処理

各クエリに対して

指定された橋を渡る全ての可能な順序を生成（順列）
```
for bridge_order in permutations(bridge_indices):
```
各順序において、橋の渡り方（どちら向きに渡るか）の全パターンを検討
- 各橋は島U→島Vまたは島V→島Uのどちらかの方向に渡れる
- 2^K通りの渡り方がある（Kは渡る橋の数）
- 各橋について両方向からの到達時間を追跡
最短時間の計算
- 現在位置から次の橋の始点までの移動時間
- 橋を渡る時間
- 最後の橋から島Nまでの移動時間
  を全て考慮して最小値を求める

4. 実装のポイント

状態追跡:
- time_to_uとtime_to_v: 島Uと島Vに到達する最小時間
- current_uとcurrent_v: 現在の位置
最適化:
- 橋を渡る順序を全て試す（順列）
- 各橋の渡り方（方向）を考慮
- 各ステップで最小時間を更新
最終結果:
- 全ての橋を渡る時間の合計 + 島間の移動時間の最小値

ACコード1

ac.py

import logging
from itertools import permutations

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:  # ハンドラが存在しない場合のみ追加
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    
    logger.debug("ロガーのセットアップが完了しました。デバッグモード: %s", debug_mode)
    return logger

def io_func():
    # 入力処理
    num_islands, num_bridges = map(int, input().split())
    bridges = []
    for i in range(num_bridges):
        island_u, island_v, time = [int(i) - 1 for i in input().split()]
        time += 1  # 時間を調整
        bridges.append([island_u, island_v, time])
    
    num_queries = int(input())
    queries = []
    for _ in range(num_queries):
        num_bridges_to_cross = int(input())
        bridge_indices = [int(i) - 1 for i in input().split()]
        queries.append((num_bridges_to_cross, bridge_indices))
    
    return num_islands, num_bridges, bridges, num_queries, queries

def solve(num_islands, num_bridges, bridges, num_queries, queries):
    logger = setup_logger(False)
    logger.debug(f"島の数: {num_islands}, 橋の数: {num_bridges}")
    logger.debug(f"橋の情報: {bridges}")
    
    # 最短経路の初期化
    INF = 10 ** 18
    distances = [[INF] * num_islands for _ in range(num_islands)]
    for i in range(num_islands):
        distances[i][i] = 0
    
    # 橋の情報から直接つながっている島間の距離を設定
    for island_u, island_v, time in bridges:
        distances[island_u][island_v] = min(distances[island_u][island_v], time)
        distances[island_v][island_u] = min(distances[island_v][island_u], time)
    
    logger.debug(f"初期距離行列: {distances}")
    
    # ワーシャルフロイド法で全ての島間の最短距離を計算
    for k in range(num_islands):
        for i in range(num_islands):
            for j in range(num_islands):
                distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
    
    logger.debug(f"ワーシャルフロイド法適用後の距離行列: {distances}")
    
    results = []
    # 各クエリに対する処理
    for query_idx, (num_bridges_to_cross, bridge_indices) in enumerate(queries):
        logger.debug(f"クエリ {query_idx+1}: 渡る橋の数 {num_bridges_to_cross}, 橋のインデックス {bridge_indices}")
        
        # 渡る橋の総時間
        total_bridge_time = 0
        for bridge_idx in bridge_indices:
            total_bridge_time += bridges[bridge_idx][2]
        
        logger.debug(f"渡る橋の総時間: {total_bridge_time}")
        
        # 橋を渡る順序の全ての組み合わせを試す
        min_time = INF
        for bridge_order in permutations(bridge_indices):
            logger.debug(f"橋の順序: {bridge_order}")
            
            # 現在の位置と時間の状態を追跡
            time_to_u = 0  # 島Uに到達する最小時間
            time_to_v = 0  # 島Vに到達する最小時間
            current_u = 0  # 現在のU位置（最初は島1）
            current_v = 0  # 現在のV位置（最初は島1）
            
            logger.debug(f"初期状態: time_to_u={time_to_u}, time_to_v={time_to_v}, current_u={current_u}, current_v={current_v}")

            for bridge_idx in bridge_order:
                island_u, island_v, _ = bridges[bridge_idx]
                logger.debug(f"橋{bridge_idx}を検討中: 島{island_u}から島{island_v}への橋")
                
                # 次の橋の始点に移動する最小時間を計算
                next_time = min(time_to_u + distances[current_u][island_u], 
                               time_to_v + distances[current_v][island_u])
                logger.debug(f"  島{island_u}への移動時間計算: U({current_u})から={time_to_u + distances[current_u][island_u]}, V({current_v})から={time_to_v + distances[current_v][island_u]}, 最小値={next_time}")

                # 次の橋の終点に移動する最小時間を計算
                time_to_u = min(time_to_u + distances[current_u][island_v], 
                               time_to_v + distances[current_v][island_v])
                time_to_v = next_time
                
                # 現在位置を更新
                current_u = island_u
                current_v = island_v
            
            # 最後に島Nまでの時間を計算
            final_time_u = time_to_u + distances[current_u][num_islands - 1]
            final_time_v = time_to_v + distances[current_v][num_islands - 1]
            
            # 最小時間を更新
            min_time = min(min_time, final_time_u, final_time_v)
            
            logger.debug(f"この順序での最小時間: {min(final_time_u, final_time_v)}")
        
        # 結果に橋を渡る時間を加算
        result = min_time + total_bridge_time
        results.append(result)
        logger.debug(f"クエリ {query_idx+1} の結果: {result}")
    
    return results

def main():
    num_islands, num_bridges, bridges, num_queries, queries = io_func()
    results = solve(num_islands, num_bridges, bridges, num_queries, queries)
    
    # 結果を出力
    for result in results:
        print(result)

if __name__ == "__main__":
    main()

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up