概要

\(N \le 18\) と小さいので、訪れた頂点集合をビットで持つ \(2^N\) 状態の DP を使います。
各単純パスを「使った頂点集合」と「最後の頂点」で数え上げれば、パス数とスコア総和の両方を効率よく求められます。

考察

この問題で求めたいのは、\(S\) から \(T\) への全単純パスの

\[ \frac{\text{スコアの総和}}{\text{単純パスの総数}} \]

です。

素朴な DFS 列挙は厳しい

単純パスを 1 本ずつ DFS で列挙する方法を考えたくなりますが、単純パスの本数は非常に多くなり得ます。
たとえばグラフがほぼ完全グラフに近いと、通り方の候補は爆発的に増えます。

\(N=18\) でも、単純パスを全部列挙するのは現実的ではありません。

---

重要な気づき 1: 「どの頂点を使ったか」を状態にすると重複なく数えられる

単純パスでは同じ頂点を 2 回使えないので、

• 今までに使った頂点集合
• 今いる頂点

を状態に持てば、単純パスを自然に表現できます。

そこで

\[ \text{cnt}[mask][v] \]

を

• \(S\) から出発し
• 訪れた頂点集合がちょうど \(mask\)
• 最後の頂点が \(v\)

である単純パスの本数

と定義します。

この状態なら、\(v\) からまだ訪れていない隣接頂点 \(to\) へ 1 歩進むだけで遷移できます。

---

重要な気づき 2: スコアは「順番」ではなく「使った頂点集合」で決まる

パスのスコアは、そのパスに含まれる頂点の満足度の総和です。

つまり、あるパスが使った頂点集合を \(mask\) とすると、そのスコアは

\[ \sum_{i \in mask} c_i \]

です。

ここで大事なのは、スコアは頂点を通る順番に依らないことです。
同じ頂点集合を使う別のパスが複数あっても、スコアは同じです。

たとえば使った頂点が \(\{S, a, b, T\}\) なら、
\(S \to a \to b \to T\) でも \(S \to b \to a \to T\) でも、スコアは

\[ c_S + c_a + c_b + c_T \]

で同じです。

したがって、まず各 \((mask, T)\) に対するパス本数だけ数えておけば、

\[ \text{スコア総和} = \sum_{mask:\, S,T \in mask} \text{cnt}[mask][T] \times \text{sum}(mask) \]

とできます。
ここで \(\text{sum}(mask)\) は集合 \(mask\) に含まれる頂点の満足度総和です。

この発想により、スコア用の複雑な DP を作らずに済みます。

---

重要な気づき 3: \(T\) に着いたらそこで終了

求めたいのは \(S\) から \(T\) へのパスです。
したがって、DP 中で最後の頂点が \(T\) になった状態は、もうそれ以上伸ばす必要がありません。

コードでも if v == T: continue としていて、これにより無駄な遷移を省いています。

アルゴリズム

1. グラフをビット集合で持つ

各頂点 \(v\) について、隣接頂点集合をビットマスク adj[v] で持ちます。
こうすると「まだ訪れていない隣接頂点」は

\[ adj[v] \,\&\, \sim mask \]

で一気に求められます。

---

2. 各頂点集合の満足度総和 mask_sum を前計算

mask_sum[mask] を

\[ mask に含まれる頂点の c の総和 \]

とします。

これは最下位ビットを使って

\[ mask\_sum[mask] = mask\_sum[mask \setminus \{lsb\}] + c[\text{lsb に対応する頂点}] \]

で \(O(2^N)\) で前計算できます。

---

3. DP で単純パス数を数える

DP の定義は次です。

\[ \text{cnt}[mask][v] = S から始まり、訪問集合が mask で、最後が v である単純パスの本数 \]

初期状態は

\[ \text{cnt}[1 \ll S][S] = 1 \]

です。

遷移は、

• 現在 cnt[mask][v] = ways
• \(v\) の隣接頂点のうち、まだ mask に入っていない頂点 to

に対して

\[ \text{cnt}[mask \cup \{to\}][to] += \text{cnt}[mask][v] \]

とします。

これで、同じ頂点を 2 回使わない単純パスだけが数え上げられます。

---

4. 最後に平均を計算

\(S\) と \(T\) の両方を含む全ての mask について、

• cnt[mask][T] を単純パス数として加算
• cnt[mask][T] * mask_sum[mask] をスコア総和に加算

します。

すると

• total_cnt = \(S\) から \(T\) への単純パス総数
• total_score = それらのスコア総和

が得られるので、答えは

\[ \frac{total\_score}{total\_cnt} \]

です。

計算量

• 時間計算量: \(O(N^2 2^N)\)
• 空間計算量: \(O(N 2^N)\)

補足

mask_sum の前計算は \(O(2^N)\) です。
DP の遷移は各状態から未訪問の隣接頂点へ進むので、最悪では \(O(N^2 2^N)\) 程度になります。

\(N \le 18\) なら

\[ N 2^N \approx 18 \times 262144 \approx 4.7 \times 10^6 \]

で、十分実行可能です。

実装のポイント

• 頂点番号は入力では \(1\) 始まりですが、実装では \(0\) 始まりに直しています。

• adj[v] をビット集合で持つと、未訪問の隣接頂点列挙が高速になります。

• cnt[mask][v] は 2 次元配列でも書けますが、コードでは 1 次元配列に平坦化して高速化しています。

• mask_sum を前計算しておくことで、最後の集計時に毎回頂点和を計算せずに済みます。

• v == T の状態から遷移しないことで、不要な計算を減らしています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)
    S = next(it) - 1
    T = next(it) - 1

    c = [next(it) for _ in range(N)]

    size = 1 << N

    bit_to_idx = [0] * size
    for i in range(N):
        bit_to_idx[1 << i] = i

    adj = [0] * N
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        adj[u] |= 1 << v
        adj[v] |= 1 << u

    mask_sum = [0] * size
    for mask in range(1, size):
        lsb = mask & -mask
        mask_sum[mask] = mask_sum[mask ^ lsb] + c[bit_to_idx[lsb]]

    base_of = [i * N for i in range(size)]
    cnt = [0] * (size * N)

    sbit = 1 << S
    tbit = 1 << T
    cnt[base_of[sbit] + S] = 1

    for mask in range(size):
        if (mask & sbit) == 0:
            continue
        base = base_of[mask]
        bits = mask
        while bits:
            bitv = bits & -bits
            bits -= bitv
            v = bit_to_idx[bitv]
            if v == T:
                continue
            ways = cnt[base + v]
            if ways == 0:
                continue
            avail = adj[v] & ~mask
            while avail:
                bit = avail & -avail
                avail -= bit
                to = bit_to_idx[bit]
                cnt[base_of[mask | bit] + to] += ways

    need = sbit | tbit
    total_cnt = 0
    total_score = 0
    for mask in range(size):
        if (mask & need) == need:
            ways = cnt[base_of[mask] + T]
            if ways:
                total_cnt += ways
                total_score += ways * mask_sum[mask]

    print("{:.15f}".format(total_score / total_cnt))

if __name__ == "__main__":
    main()

---

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