Overview

Since \(N \le 18\) is small, we use a DP with \(2^N\) states where the set of visited vertices is represented as a bitmask. By counting each simple path using the “set of used vertices” and the “last vertex,” we can efficiently compute both the number of paths and the total score.

Approach

What we want to find is, for all simple paths from \(S\) to \(T\):

\[ \frac{\text{total score}}{\text{total number of simple paths}} \]

Naive DFS enumeration is infeasible

One might think of enumerating simple paths one by one using DFS, but the number of simple paths can be extremely large. For example, if the graph is close to a complete graph, the number of possible routes explodes.

Even with \(N=18\), enumerating all simple paths is not practical.

---

Key Insight 1: Using “which vertices have been visited” as a state allows counting without duplicates

Since a simple path cannot visit the same vertex twice, if we maintain:

• The set of vertices visited so far
• The current vertex

as our state, we can naturally represent simple paths.

Therefore, we define

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

as the number of simple paths that:

• Start from \(S\)
• Have visited exactly the set of vertices \(mask\)
• End at vertex \(v\)

With this state, we can transition simply by taking one step from \(v\) to an adjacent vertex \(to\) that has not yet been visited.

---

Key Insight 2: The score depends on the “set of used vertices,” not the order

The score of a path is the sum of satisfaction values of the vertices included in that path.

In other words, if the set of vertices used by a path is \(mask\), then its score is

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

The important point here is that the score does not depend on the order in which vertices are visited. Even if there are multiple different paths using the same set of vertices, the score is the same.

For example, if the used vertices are \(\{S, a, b, T\}\), then whether the path is \(S \to a \to b \to T\) or \(S \to b \to a \to T\), the score is

\[ c_S + c_a + c_b + c_T \]

which is the same.

Therefore, if we first count only the number of paths for each \((mask, T)\), then

\[ \text{total score} = \sum_{mask:\, S,T \in mask} \text{cnt}[mask][T] \times \text{sum}(mask) \]

where \(\text{sum}(mask)\) is the sum of satisfaction values of the vertices in the set \(mask\).

This insight eliminates the need to create a complex DP for tracking scores.

---

Key Insight 3: Once we reach \(T\), the path ends there

What we want are paths from \(S\) to \(T\). Therefore, any DP state where the last vertex is \(T\) does not need to be extended further.

In the code, this is handled with if v == T: continue, which avoids unnecessary transitions.

Algorithm

1. Store the graph using bit sets

For each vertex \(v\), store the set of adjacent vertices as a bitmask adj[v]. This way, “adjacent vertices not yet visited” can be computed all at once as

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

---

2. Precompute the satisfaction sum mask_sum for each vertex set

Define mask_sum[mask] as

\[ \text{the sum of } c \text{ values for vertices in } mask \]

Using the lowest set bit, this can be precomputed in \(O(2^N)\) as

\[ mask\_sum[mask] = mask\_sum[mask \setminus \{lsb\}] + c[\text{vertex corresponding to lsb}] \]

---

3. Count simple paths with DP

The DP is defined as follows:

\[ \text{cnt}[mask][v] = \text{number of simple paths starting from } S \text{, with visited set } mask \text{, ending at } v \]

The initial state is

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

The transition is: for the current state cnt[mask][v] = ways, for each adjacent vertex to of \(v\) that is not yet in mask:

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

This ensures that only simple paths (which do not visit the same vertex twice) are counted.

---

4. Compute the average at the end

For all mask that contain both \(S\) and \(T\):

• Add cnt[mask][T] to the total number of simple paths
• Add cnt[mask][T] * mask_sum[mask] to the total score

Then:

• total_cnt = total number of simple paths from \(S\) to \(T\)
• total_score = total score of those paths

and the answer is

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

Complexity

• Time complexity: \(O(N^2 2^N)\)
• Space complexity: \(O(N 2^N)\)

Notes

The precomputation of mask_sum is \(O(2^N)\). The DP transitions move from each state to unvisited adjacent vertices, so in the worst case it is approximately \(O(N^2 2^N)\).

For \(N \le 18\):

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

which is well within the time limit.

Implementation Details

• Vertex indices are \(1\)-based in the input, but converted to \(0\)-based in the implementation.

• Storing adj[v] as bit sets makes enumerating unvisited adjacent vertices fast.

• cnt[mask][v] can be written as a 2D array, but in the code it is flattened into a 1D array for speed.

• Precomputing mask_sum avoids recalculating the vertex sum each time during the final aggregation.

• Not transitioning from states where v == T reduces unnecessary computation.

  Source Code

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

---

This editorial was generated by gpt-5.4-high.