Overview

This problem asks us to consider all simple paths (paths that do not visit the same vertex twice) from a start vertex \(S\) to an end vertex \(T\) in a given graph, and compute the average of their scores (the sum of satisfaction values of the vertices along the path).

Since the number of vertices \(N\) is at most 18, which is small, we can solve this efficiently using bitmask DP (bitset DP) to compute the total number of simple paths and the total sum of their scores.

Analysis

1. Properties of Simple Paths

Since simple paths do not visit the same vertex twice, we need to keep track of which vertices have already been visited. Also, a path is completed upon reaching the endpoint \(T\). We do not need to consider paths that pass through \(T\) and go to other vertices before returning to \(T\), as such paths would violate the “no repeated vertices” condition of simple paths.

2. Why Naive Search Doesn’t Work

If we try to naively enumerate all paths from \(S\) to \(T\) using depth-first search (DFS) or similar methods, the number of paths can grow explosively depending on the graph structure, making it impossible to finish within the time limit.

3. Efficiency Through Bitmask DP

The constraint \(N \le 18\) suggests that we can manage the “set of visited vertices” as a bitmask (\(2^N\) possibilities). By using “which vertex we are currently at and which vertices have been visited” as the state, we can avoid redundant computations.

Algorithm

State Definition

We prepare the following 2 DP tables:

• \(dp\_count[mask][u]\): The number of simple paths from \(S\) such that the set of visited vertices is \(mask\) and the current vertex is \(u\).
• \(dp\_score[mask][u]\): The total sum of scores of simple paths from \(S\) such that the set of visited vertices is \(mask\) and the current vertex is \(u\).

※ Not including the endpoint \(T\) in \(mask\) makes the implementation smoother (since we stop the search upon reaching \(T\)).

Initial State

• Let \(S_{idx}\) be \(S\) in 0-indexed form:
• \(mask = (1 \ll S_{idx})\)
• \(dp\_count[mask][S_{idx}] = 1\)
• \(dp\_score[mask][S_{idx}] = c_{S_{idx}}\)

Transitions

From the current state \((mask, u)\), we consider moving to an adjacent vertex \(v\).

1. If \(v = T\) (reached the endpoint):
   • Add \(dp\_count[mask][u]\) to the total path count.
   • Add \(dp\_score[mask][u] + dp\_count[mask][u] \times c_T\) to the total score sum.
2. If \(v \neq T\) and \(v\) is unvisited (the \(v\)-th bit of \(mask\) is 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\)

Final Answer

Output (total score sum) \(\div\) (total path count).

Complexity

• Time Complexity: \(O(2^{N-1} \cdot N^2)\)
  • The number of states is \(2^{N-1} \times (N-1)\).
  • Each state requires traversing the adjacency list (at most \(N\) times) for transitions.
  • When \(N=18\), this is approximately \(2^{17} \times 17^2 \approx 3.8 \times 10^7\), which can fit within the time limit even in Python with appropriate optimizations.
• Space Complexity: \(O(2^{N-1} \cdot N)\)
  • Depends on the size of the DP tables.

Implementation Tips

• Bit manipulation tricks: In Python, techniques like while mask: u_bit = mask & -mask can be used to efficiently loop over only the set bits (visited vertices).

• Handling the endpoint: By not including the endpoint \(T\) in the DP transitions and instead adding to “accumulation variables” the moment \(T\) is found as an adjacent vertex, the number of states to manage is halved (\(2^{N-1}\)), resulting in speedup.

• Fast I/O: Even though \(N, M\) are small, the graph construction and number of loop iterations can be large, so it is advisable to use bulk input methods like sys.stdin.read().split().

  Source Code

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

---

This editorial was generated by gemini-3-flash-thinking.