概要

この問題は、与えられたグラフにおいて始点 \(S\) から終点 \(T\) へのすべての単純パス（同じ頂点を2回通らない経路）を考え、それらのスコア（経路上の頂点の満足度の合計）の平均値を求める問題です。

頂点数 \(N\) が最大 18 と小さいため、ビット DP（bitset DP） を用いて、すべての単純パスの個数とそのスコアの総和を効率的に計算することで解くことができます。

考察

1. 単純パスの性質

単純パスは同じ頂点を2回訪れないため、一度訪れた頂点を記録しておく必要があります。また、終点 \(T\) に到達した時点でそのパスは完成となります。\(T\) を通り過ぎて他の頂点へ行き、再び \(T\) に戻るような経路は「単純パス」の条件（頂点の重複禁止）に反するため考慮する必要はありません。

2. なぜ素朴な探索ではダメなのか

\(S\) から \(T\) へのパスを深さ優先探索（DFS）などで愚直に列挙しようとすると、グラフの構造によってはパスの数が爆発的に増えてしまい、実行時間制限に間に合いません。

3. ビット DP による効率化

\(N \le 18\) という制約は、「訪れた頂点の集合」をビットマスク（\(2^N\) 通り）で管理できることを示唆しています。 「現在どの頂点にいて、どの頂点を訪問済みか」を状態として持つことで、重複した計算を避けることができます。

アルゴリズム

状態定義

以下の 2 つの DP テーブルを用意します。

• \(dp\_count[mask][u]\): 訪れた頂点の集合が \(mask\) で、現在の頂点が \(u\) であるような \(S\) からの単純パスの個数。
• \(dp\_score[mask][u]\): 訪れた頂点の集合が \(mask\) で、現在の頂点が \(u\) であるような \(S\) からの単純パスのスコアの総和。

※ ここで \(mask\) には終点 \(T\) を含めないようにすると、実装がスムーズになります（\(T\) に着いたら探索を終了するため）。

初期状態

• \(S\) を 0-indexed で \(S_{idx}\) とすると：
• \(mask = (1 \ll S_{idx})\)
• \(dp\_count[mask][S_{idx}] = 1\)
• \(dp\_score[mask][S_{idx}] = c_{S_{idx}}\)

遷移

現在の状態 \((mask, u)\) から、隣接する頂点 \(v\) へ移動することを考えます。

1. \(v = T\) の場合（終点に到達）:
   • 全体のパス数に \(dp\_count[mask][u]\) を加算。
   • 全体のスコア総和に \(dp\_score[mask][u] + dp\_count[mask][u] \times c_T\) を加算。
2. \(v \neq T\) かつ \(v\) が未訪問の場合（\(mask\) の \(v\) 番目のビットが 0）:
   • \(next\_mask = mask \cup \{v\}\)
   • \(dp\_count[next\_mask][v] += dp\_count[mask][u]\)
   • \(dp\_score[next\_mask][v] += dp\_score[mask][u] + dp\_count[mask][u] \times c_v\)

最終的な答え

（全体のスコア総和）\(\div\)（全体のパス数）を出力します。

計算量

• 時間計算量: \(O(2^{N-1} \cdot N^2)\)
  • 状態数は \(2^{N-1} \times (N-1)\) です。
  • 各状態からの遷移に、隣接リストの走査（最大 \(N\) 回）がかかります。
  • \(N=18\) のとき \(2^{17} \times 17^2 \approx 3.8 \times 10^7\) 程度であり、Python でも工夫次第で制限時間内に収まります。
• 空間計算量: \(O(2^{N-1} \cdot N)\)
  • DP テーブルのサイズに依存します。

実装のポイント

• ビット演算の工夫: Python では while mask: u_bit = mask & -mask のようなテクニックを使うことで、ビットが立っている場所（訪問済み頂点）のみを効率的にループできます。

• 終点の扱い: 終点 \(T\) を DP の遷移に含めず、隣接頂点に \(T\) が見つかった瞬間に「集計用変数」へ加算するように実装すると、管理する状態数が半分（\(2^{N-1}\)）になり高速化されます。

• 高速な入出力: \(N, M\) が小さくても、グラフの構築やループ回数が多いため、sys.stdin.read().split() などで一括入力を行うのが無難です。

  ソースコード

import sys

def solve():
    # Read all input at once for efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    if not input_data:
        return
    
    # N: number of spots, M: number of roads
    # S_orig: start spot (0-indexed), T_orig: target spot (0-indexed)
    N = int(input_data[0])
    M = int(input_data[1])
    S_orig = int(input_data[2]) - 1
    T_orig = int(input_data[3]) - 1
    
    # costs: satisfaction of each spot
    costs = [int(input_data[i + 4]) for i in range(N)]
    
    # Adjacency list for the graph
    adj = [[] for _ in range(N)]
    idx = 4 + N
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx + 1]) - 1
        adj[u].append(v)
        adj[v].append(u)
        idx += 2

    # Since we are considering simple paths from S to T, 
    # T can only be the final node of the path.
    # We use a bitmask DP over the set of nodes excluding T.
    others = [i for i in range(N) if i != T_orig]
    num_others = N - 1
    mapping = {node: i for i, node in enumerate(others)}
    
    # Pre-calculate neighbor info and connections to T
    adj_info = [[] for _ in range(num_others)]
    has_T = [False] * num_others
    for u_mapped, u_orig in enumerate(others):
        for v_orig in adj[u_orig]:
            if v_orig == T_orig:
                has_T[u_mapped] = True
            else:
                v_mapped = mapping[v_orig]
                adj_info[u_mapped].append((1 << v_mapped, v_mapped, costs[v_orig]))
    
    # dp_count[u_mapped][mask]: number of simple paths from S to u_mapped visiting nodes in mask
    # dp_score[u_mapped][mask]: sum of scores of these paths
    dp_count = [[0] * (1 << num_others) for _ in range(num_others)]
    dp_score = [[0] * (1 << num_others) for _ in range(num_others)]
    
    S_mapped = mapping[S_orig]
    dp_count[S_mapped][1 << S_mapped] = 1
    dp_score[S_mapped][1 << S_mapped] = costs[S_orig]
    
    total_path_count = 0
    total_path_score = 0
    cost_T = costs[T_orig]
    
    # Iterate through all possible bitmasks representing visited nodes in 'others'
    for mask in range(1, 1 << num_others):
        m_copy = mask
        while m_copy:
            # Get the index of the lowest set bit
            u_bit = m_copy & -m_copy
            u_mapped = u_bit.bit_length() - 1
            m_copy ^= u_bit
            
            # Current number of paths and their score sum ending at u_mapped with mask
            c_u = dp_count[u_mapped][mask]
            if c_u == 0:
                continue
            s_u = dp_score[u_mapped][mask]
            
            # If current node has an edge to T, add these paths to the total
            if has_T[u_mapped]:
                total_path_count += c_u
                total_path_score += s_u + c_u * cost_T
            
            # Extend path to neighbors not already in the mask
            for v_bit, v_mapped, cost_v in adj_info[u_mapped]:
                if not (mask & v_bit):
                    new_mask = mask | v_bit
                    dp_count[v_mapped][new_mask] += c_u
                    dp_score[v_mapped][new_mask] += s_u + c_u * cost_v
                    
    # Output the average score (total sum divided by total number of simple paths)
    if total_path_count > 0:
        print(total_path_score / total_path_count)
    else:
        # Should not be reached based on problem constraints
        print(0.0)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。