概要

都市1を出発して時間制限 \(T\) 以内に複数の都市を訪問し、ミッションの条件を満たして報酬を最大化する問題。全ミッションに登場する都市が高々14種類であることを利用し、巡回セールスマン問題(TSP)型のビットマスクDPで解く。

考察

重要な気づき

1. 重要な都市は少ない: すべてのミッションに登場する都市の種類数は高々14。都市1を加えても高々15個。ミッション達成に関係するのはこれらの都市を訪問したかどうかだけ。

2. 素朴なアプローチの問題点: 都市が \(N \leq 10^4\) 個あり、全探索で訪問順を考えるのは不可能。しかし「どの重要な都市を訪問したか」だけが報酬に影響するため、重要な都市の部分集合のみを考えればよい。

3. 最短経路の利用: 重要な都市間の移動は、途中の経路に関わらず最短距離で移動すれば最適。よって事前にDijkstraで重要都市間の最短距離を求めておけばよい。

4. ビットマスクDPでTSP: 重要な都市が最大15個なので、訪問済み集合をビットマスクで管理するDP（状態数 \(2^{15} \times 15\)）で、各部分集合を訪問する最小コストを計算できる。

アルゴリズム

1. 重要都市の特定: ミッションに登場する全都市と都市1をまとめ、インデックスを振る（最大15個）。

2. 最短距離の前計算: 各重要都市を始点としてDijkstraを実行し、重要都市間の最短距離行列 \(\text{dist}[i][j]\) を構築する。

3. ビットマスクDP:

   • 状態: \(dp[\text{mask}][i]\) = 重要都市の訪問済み集合が \(\text{mask}\) で、現在都市 \(i\) にいるときの最小移動時間
   • 初期状態: \(dp[1 \ll \text{start}][\text{start}] = 0\)（都市1にコスト0で到達）
   • 遷移: 未訪問の重要都市 \(v\) に移動 → \(dp[\text{mask} | (1 \ll v)][v] = \min(dp[\text{mask}][u] + \text{dist}[u][v])\)

4. 各マスクの最小コスト集約: \(\min\_cost[\text{mask}] = \min_i dp[\text{mask}][i]\)

5. 報酬計算: 各マスクについて、含まれるミッションの報酬合計を計算。コストが \(T\) 以下のマスクの中で報酬最大のものを答えとする。

計算量

• 時間計算量: \(O(L \cdot (N + M) \log N + 2^L \cdot L^2 + 2^L \cdot K)\)
  • \(L\) は重要都市数（\(\leq 15\)）
  • Dijkstra: \(L\) 回実行で \(O(L \cdot (N + M) \log N)\)
  • ビットマスクDP: \(O(2^L \cdot L^2)\)
  • 報酬集計: \(O(2^L \cdot K)\)
• 空間計算量: \(O(2^L \cdot L + N)\)

実装のポイント

• dist[u][v]はDijkstraで求める: 重要都市間にエッジがなくても、中間の一般都市を経由する最短路が存在する場合がある。重要都市のみでグラフを縮約してはいけない。

• 再訪問の扱い: DP遷移で未訪問都市のみに遷移しているが、これで正しい。なぜなら \(\text{dist}[u][v]\) は既に任意の中間都市（訪問済み都市含む）を経由した最短路なので、既訪問都市を経由して遠回りする経路も暗黙的に考慮されている。

• 都市1は常に訪問済み: 出発点なので、ビットマスクの初期状態に都市1のビットを立てておく。ミッションに都市1が含まれていても自動的に満たされる。

• INFの扱い: 到達不能な都市ペアが存在しうるため、距離が INF のまま遷移しないよう注意する。

  ソースコード

import heapq
import sys
from itertools import combinations

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    def rd():
        nonlocal idx
        val = int(input_data[idx]); idx += 1; return val

    N = rd(); M = rd(); K = rd(); T = rd()

    # Build adjacency list
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = rd(); v = rd(); w = rd()
        graph[u].append((v, w))

    # Read missions
    missions = []
    all_cities = set()
    for _ in range(K):
        sz = rd()
        cities = []
        for __ in range(sz):
            cities.append(rd())
        p = rd()
        missions.append((cities, p))
        all_cities.update(cities)

    # Important cities: all cities appearing in missions + city 1
    all_cities.add(1)
    important = sorted(all_cities)
    num_imp = len(important)
    
    # Map important cities to indices
    city_to_idx = {}
    for i, c in enumerate(important):
        city_to_idx[c] = i

    # Compute shortest paths between all pairs of important cities using Dijkstra
    # We need dist[i][j] = shortest path from important[i] to important[j]
    INF = float('inf')
    dist = [[INF] * num_imp for _ in range(num_imp)]

    for si in range(num_imp):
        src = important[si]
        # Dijkstra from src
        d = [INF] * (N + 1)
        d[src] = 0
        pq = [(0, src)]
        while pq:
            cost, u = heapq.heappop(pq)
            if cost > d[u]:
                continue
            for v, w in graph[u]:
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    heapq.heappush(pq, (d[v], v))
        for di in range(num_imp):
            dist[si][di] = d[important[di]]

    # Now we have important cities indexed 0..num_imp-1
    # City 1 is at index city_to_idx[1]
    start = city_to_idx[1]

    # Mission cities as bitmasks over important city indices
    # For each mission, compute the bitmask of required cities (excluding city 1 if present, 
    # since city 1 is always visited... actually city 1 IS always visited)
    # Actually, we use bitmask over all important cities. City 1 is always visited.
    
    # Important cities that are NOT city 1 (these are the ones we need to decide to visit)
    # But for TSP we consider all important cities.
    
    # Bitmask TSP: state = (current_city_index, visited_set_bitmask), value = min cost
    # visited_set_bitmask tracks which important cities have been visited
    # Start: at start, visited = {start}
    
    # num_imp <= 16 (15 mission cities + city 1)
    
    full = 1 << num_imp
    # dp[mask][i] = minimum cost to have visited exactly the important cities in mask, 
    # currently at important city i
    dp = [[INF] * num_imp for _ in range(full)]
    start_mask = 1 << start
    dp[start_mask][start] = 0

    for mask in range(full):
        for u in range(num_imp):
            if dp[mask][u] >= INF:
                continue
            if not (mask & (1 << u)):
                continue
            # Try going to another important city v
            for v in range(num_imp):
                if mask & (1 << v):
                    continue  # already visited (optimization, but revisiting is ok for path)
                new_mask = mask | (1 << v)
                new_cost = dp[mask][u] + dist[u][v]
                if new_cost < dp[new_mask][v]:
                    dp[new_mask][v] = new_cost
            # Also try going to already-visited city (for shorter path through it)
            # Actually we don't need to revisit already-visited important cities in TSP
            # because dist[u][v] already gives shortest path (possibly through visited cities)

    # For each mask, find the minimum cost to achieve it
    min_cost_for_mask = [INF] * full
    for mask in range(full):
        for u in range(num_imp):
            if dp[mask][u] < min_cost_for_mask[mask]:
                min_cost_for_mask[mask] = dp[mask][u]

    # For each mission, compute bitmask and reward
    mission_masks = []
    for cities, p in missions:
        bm = 0
        for c in cities:
            bm |= 1 << city_to_idx[c]
        mission_masks.append((bm, p))

    # Precompute reward for each visited mask
    reward_for_mask = [0] * full
    for mask in range(full):
        for bm, p in mission_masks:
            if (mask & bm) == bm:
                reward_for_mask[mask] += p

    ans = 0
    for mask in range(full):
        if not (mask & (1 << start)):
            continue
        if min_cost_for_mask[mask] <= T:
            if reward_for_mask[mask] > ans:
                ans = reward_for_mask[mask]

    print(ans)

main()

この解説は claude4.6opus-thinking によって生成されました。