Overview

This problem asks us to consider all simple paths from \(S\) to \(T\), compute the sum of vertex weights (satisfaction values) along each path, and find the average of these sums.
Since \(N \le 18\) is small, we can enumerate all paths using subset DP (bit DP) where vertex sets are managed with bitmasks.

Approach

If we naively “enumerate all simple paths and take the average,” the number of paths can grow exponentially depending on the graph, and brute-force DFS enumeration won’t be fast enough.

The key constraint here is \(N \le 18\).
Since we can represent vertex sets as \(2^N\) bitmasks,
a DP that tracks “which vertices have been used” as state becomes feasible.

Key Design

Since we want to compute the average, what we actually need is:

• The total number of paths
• The total sum of path scores (sum of vertex weights for each path)

So for each state, we maintain:

• dp_count[mask][v]:
  The number of simple paths from \(S\) to \(v\) where the set of visited vertices is mask
• dp_sum[mask][v]:
  The total score sum of all such paths

By transitioning both simultaneously, we can aggregate at \(T\) at the end to compute the average.

Meaning of Transitions

When moving from (mask, v) to an unvisited adjacent vertex u:

• The count is simply added:
  dp_count[mask|{u}][u] += dp_count[mask][v]
• For the score sum, we add the weight of u to the existing scores:
  Since each path gains \(c_u\),
  dp_sum[mask|{u}][u] += dp_sum[mask][v] + dp_count[mask][v] * c[u]

This formula is the core of the problem.

Algorithm

1. Read input and convert vertices to 0-indexed.
2. Instead of adjacency lists, store each vertex’s neighbors as a bitset adj[v] (for fast extraction of unvisited neighbors).
3. Initialize dp_count and dp_sum as arrays of size \(2^N \times N\).
4. Initial state:
   
   • start_mask = 1<<S
   • dp_count[start_mask][S] = 1
   • dp_sum[start_mask][S] = c[S]
5. For every mask and every endpoint v, perform transitions.
   Use nxt = adj[v] & ~mask to extract only unvisited neighbors, then iterate over each bit to update.
6. For all mask that contain \(T\):
   • total_count += dp_count[mask][T]
   • total_sum += dp_sum[mask][T]
7. The answer is the average total_sum / total_count.

Complexity

• Time complexity: \(O(2^N \cdot N^2)\) (in practice, the total over all transitions from each state to its neighbors)
• Space complexity: \(O(2^N \cdot N)\)

※ Since \(N \le 18\), this is well within the execution limits.

Implementation Notes

• Simple path guarantee is achieved by restricting u to unvisited vertices (~mask).

• Rather than directly computing the average via DP, it is safer and easier to implement by managing the count and sum separately.

• In Python, int supports arbitrary precision, so there is no overflow even when the number of paths or the total sum becomes very large.

• Bit scanning (lsb = x & -x) is used to efficiently enumerate unvisited neighbors.

  Source Code

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()

---

This editorial was generated by gpt-5.3-codex.