Cerinta completa

Logan and Veronica live in Neptune, which has houses and bidirectional roads connecting them. Each road has an assigned value, , where , and each house is numbered with a distinct integer from to .

Logan and Veronica are looking for clues and need to find the number of different paths of length from house number . Each path is characterized by a binary sequence of length , where each integer in the path is the value of for the edge in the path. Two paths are different if the binary sequences characterizing these paths are distinct. Note that they may need to visit the same house several times or use the same road several times to find all possible paths.

Given a map of Neptune, help Logan and Veronica find and print the number of different paths of length from house number to the other houses in Neptune.

Input Format

The first line contains three space-separated integers describing the respective values of (the number of houses), (the number of bidirectional roads), and (the distance they want to travel).
Each of the subsequent lines contains three space-separated integers describing the respective values of , , and that define a bidirectional road between houses and having assigned value .

Constraints

  • There may be roads connecting house to itself.
  • There may be more than one road between two houses.

Output Format

Print an integer denoting the total number of paths.

Sample Input

3 2 3
1 2 0
1 3 1

Sample Output

4

Explanation

There are four possible paths:

Thus, we print as our answer.

Limbajul de programare folosit: python3

Cod:

import sys
from functools import lru_cache

# Increase recursion depth if needed
sys.setrecursionlimit(2000000)

def solve():
    data = sys.stdin.read().split()
    if not data:
        return
    
    # Use iter for cleaner parsing
    data_iter = (int(x) for x in data)
    try:
        n = next(data_iter)
        m = next(data_iter)
        d = next(data_iter)
    except StopIteration:
        return

    # Correct list initialization using list multiplication [0] * n
    edge0 = [0] * n
    edge1 = [0] * n
    
    for _ in range(m):
        try:
            u = next(data_iter) - 1
            v = next(data_iter) - 1
            bit = next(data_iter)
        except StopIteration:
            break
        
        if bit == 0:
            edge0[u] |= (1 << v)
            if u != v:
                edge0[v] |= (1 << u) # Bidirectional edge
        else:
            edge1[u] |= (1 << v)
            if u != v:
                edge1[v] |= (1 << u) # Bidirectional edge

    # Memoized recursive function to count paths
    @lru_cache(None)
    def count_paths(length, nodes_mask):
        if length == 0:
            return 1
        
        # Calculate next_nodes for appending 0
        next_nodes0 = 0
        for u in range(n):
            if nodes_mask & (1 << u):
                next_nodes0 |= edge0[u]
        
        # Calculate next_nodes for appending 1
        next_nodes1 = 0
        for u in range(n):
            if nodes_mask & (1 << u):
                next_nodes1 |= edge1[u]
        
        ans = 0
        if next_nodes0:
            ans += count_paths(length - 1, next_nodes0)
        if next_nodes1:
            ans += count_paths(length - 1, next_nodes1)
        
        return ans

    # Start the recursive count from length d, starting house 1 (node 0)
    result = count_paths(d, 1)
    print(result)
    
    # Clear cache after the run
    count_paths.cache_clear()

solve()

Scor obtinut: 1.0

Submission ID: 464669045

Link challenge: https://www.hackerrank.com/challenges/clues-on-a-binary-path/problem

Clues on a Binary Path