概要

\(S\) から \(T\) へのすべての単純パスについて、各パス上の頂点重み（満足度）の合計を集計し、その平均を求める問題です。
\(N \le 18\) と小さいので、頂点集合をビットマスクで管理する部分集合 DP（bit DP）で全パスを数え上げます。

考察

まず「単純パスを全部列挙して平均を取る」ことをそのままやると、パス数はグラフによって指数的に増え、DFS 全列挙は間に合いません。

この制約で重要なのは \(N \le 18\) です。
頂点集合を \(2^N\) 通りのビットマスクで表せるので、
「どの頂点を使ったか」を状態に持つ DP が可能になります。

重要な設計

平均を求めたいので、本来ほしいのは

• パスの本数
• パススコア（各パスの頂点重み和）の総和

の 2 つです。
そこで状態ごとに次を持ちます：

• dp_count[mask][v]：
  「使った頂点集合が mask、終点が v」である \(S \to v\) の単純パス本数
• dp_sum[mask][v]：
  上記パスたちのスコア総和

この 2 つを同時に遷移させると、最後に \(T\) で合流して平均を出せます。

遷移の意味

(mask, v) から未訪問隣接頂点 u に進むとき：

• 本数はそのまま加算：
  dp_count[mask|{u}][u] += dp_count[mask][v]
• スコア総和は、既存スコアに u の重みを足す：
  各パスで \(c_u\) 増えるので
  dp_sum[mask|{u}][u] += dp_sum[mask][v] + dp_count[mask][v] * c[u]

この式がこの問題の核心です。

アルゴリズム

1. 入力を受け取り、頂点を 0-index に直す。
2. 隣接リストの代わりに、各頂点の隣接先をビット集合 adj[v] として持つ（高速に未訪問隣接を取り出すため）。
3. dp_count, dp_sum を 2^N × N で用意。
4. 初期状態：
   
   • start_mask = 1<<S
   • dp_count[start_mask][S] = 1
   • dp_sum[start_mask][S] = c[S]
5. 全 mask、全終点 v について遷移。
   nxt = adj[v] & ~mask で未訪問隣接だけを抽出し、1bit ずつ取り出して更新。
6. T を含むすべての mask について
   • total_count += dp_count[mask][T]
   • total_sum += dp_sum[mask][T]
7. 答えは平均 total_sum / total_count。

計算量

• 時間計算量: \(O(2^N \cdot N^2)\)（実装上は「各状態から隣接先へ」の合計）
• 空間計算量: \(O(2^N \cdot N)\)

※ \(N \le 18\) なので十分実行可能です。

実装のポイント

• 単純パス保証は u を「未訪問（~mask）」に限定することで実現。

• 平均を直接 DP せず、本数と総和を別々に管理するのが安全で実装しやすい。

• Python では int が多倍長なので、パス数・総和が大きくなってもオーバーフローしません。

• ビット走査（lsb = x & -x）で未訪問隣接を高速列挙している点が効率的です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline

    N, M, S, T = map(int, input().split())
    S -= 1
    T -= 1

    c = [int(input()) for _ in range(N)]

    adj = [0] * N
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u] |= 1 << v
        adj[v] |= 1 << u

    size = 1 << N

    # dp_count[mask][v]: number of simple paths from S to v using exactly vertices in mask
    # dp_sum[mask][v]: total score sum over those paths
    dp_count = [[0] * N for _ in range(size)]
    dp_sum = [[0] * N for _ in range(size)]

    start_mask = 1 << S
    dp_count[start_mask][S] = 1
    dp_sum[start_mask][S] = c[S]

    for mask in range(size):
        if (mask & start_mask) == 0:
            continue
        for v in range(N):
            cnt = dp_count[mask][v]
            if cnt == 0:
                continue
            sm = dp_sum[mask][v]

            nxt = adj[v] & (~mask)
            while nxt:
                lsb = nxt & -nxt
                u = lsb.bit_length() - 1
                nmask = mask | lsb
                dp_count[nmask][u] += cnt
                dp_sum[nmask][u] += sm + cnt * c[u]
                nxt ^= lsb

    total_count = 0
    total_sum = 0
    bit_t = 1 << T
    for mask in range(size):
        if (mask & bit_t) == 0:
            continue
        total_count += dp_count[mask][T]
        total_sum += dp_sum[mask][T]

    ans = total_sum / total_count
    print("{:.10f}".format(ans))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。