Special Node Distance - Teradata Online Assessment IIT R

Problem Preview

"Pattern: 3 QS You are given an undirected connected graph with **N nodes** and **M edges**. The nodes are numbered from `0` to `N-1`. Each edge connects two nodes and normally has a weight of `1`. You are also given: * A **source node** `S` * A **special node** `V` Your task is to find the minimum distance from the source node `S` to every other node. ### Special Rule Whenever a path reaches the special node `V`, the cost of reaching `V` becomes `0`. Moreover, after reaching `V`, **every node that is directly connected to `V` can also be reached with zero additional cost**. In other words, the special node acts as a zero-cost node: moving to `V` costs `0`, and moving from `V` to any of its adjacent nodes also costs `0`. Return an array `dist` where `dist[i]` represents the minimum cost required to reach node `i` from the source node `S`. ## Input Format * The first line contains an integer `N`, the number of nodes. * The second line contains an integer `M`, the number of edges. * The next `M` lines contain two integers `u` and `v`, representing an undirected edge between nodes `u` and `v`. * The next line contains an integer `S`, the source node. * The last line contains an integer `V`, the special node. ## Output Format Print `N` integers where the `i`-th integer represents the minimum distance from `S` to node `i`. ## Example ### Input ```text 5 5 0 1 1 2 2 3 3 4 1 3 2 0 ``` ### Output ```text 0 1 1 1 2 ``` ### Explanation The source node is `2` and the special node is `0`. The normal shortest distances from node `2` are: * `dist[2] = 0` * `dist[1] = 1` * `dist[3] = 1` * `dist[0] = 2` * `dist[4] = 2` Therefore, the resulting distance array is: ```text 0 1 1 1 2 ```"