Official Solution (C++)

Explanation

The first step is to calculate the length and probability of each possible path. We can do this using DFS. We start of with a probability of 1, or 100%. Then, for each node, we divide the current path's probability by the number of possible next moves.

For example, if node 1 is connected to nodes 2 and 3, the probability of reaching node 2 is $\frac{1}{2}$, or $0.5$, and the probability of reaching node 3 is also $0.5$. If node 3 is connected to nodes 4 and 5, the probability of reaching node 4 is $0.5 \div 2 = 0.25$ and the probability of reaching node 5 is also $0.25$. Let's say that nodes 2, 4, and 5 are leaf nodes. The possible paths are listed below:

• $1 \rightarrow 2$ : $0.5$
• $1 \rightarrow 3 \rightarrow 4$ : $0.25$
• $1 \rightarrow 3 \rightarrow 5$ : $0.25$

To calculate the expected length of the journey, we multiply each of the probabilities with the corresponding path length. In the example above, the expected length would be $1\cdot0.5 + 2\cdot0.25 + 2\cdot0.25 = 1.5$

In the code, for each node, we calculate the number of possible next moves by looping through the node's neighbors and counting how many are unvisited. If there are no such nodes, then the path has ended and we can add the length of the path times the probability to the final answer. Otherwise, we divide the probability (as described above) and continue the DFS.

Note: setprecision(10) sets the number of decimal places to be printed to be 10. See this for more details.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> adj;  // adjacency list
vector<bool> visited;     // stores which nodes have been visited

double ans;

void dfs(int node, int current_length, double current_probability) {

Copy
import java.util.*;

public class Journey {
	public static double ans = 0;
	public static Map<Integer, List<Integer>> adjList;  // adjacency list
	public static boolean[] visited;  // stores which nodes have been visited

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

Copy
class Point:
	"""Represents a point or node along our depth-first traversal frontier."""

	def __init__(self, node: int, length: int, probability: float):
		self.node = node
		self.length = length
		self.probability = probability


n = int(input())