NUMTRIPL - Editorial

Problem Link - Number Triples

Problem Statement

In this problem you will be given a sequence of triples of positive integers. For example:

   1  2   5
   5  2   6
   1  3   8
   8  1  11
   1  1   6
  10  1   6
  11  3   6
  10  4   8
  10  1  11

Given a pair of numbers A and B, a chain connecting A and B is a sequence of triples

A[0] W[0] A[1],~~A[1] W[1] A[2],~~A[2] W[2] A[3], ~~...A[k−2] W[k−2] A[k−1], ~~A[k−1] W[k−1] A[k]

such that

A[0] = A
A[k] = B

For each i, 0≤i<k, either the triple A[i]~~W[i]~~A[i+1] or the triple A[i+1]​ ~~W[i]~~A[i] is in the given set of triples.

The value of such a chain is the sum of the W[i]​s in the chain. For example, here is a chain connecting 1 and 11 using the triples listed above:

1~~~~~1~~~~~6,~~6~~~~~3 ~~~~~11

The value of this chain is 1+3=4.

Here is another chain connecting 1 and 11

1~~~~~6,~~6~~~~~1~~~~~10,~~10~~~~~1~~~~~11

The value of this chain is 1+1+1=3. You can verify that among all chains connecting 1 and 11 this is the one with least value.

Sometimes there may be no chains connecting the given pair of numbers. For example, there is no chain connecting 1 and 2.

You will be given a sequence of triples and a pair of numbers. Your task is to find the value of the least value chain connecting the two numbers.

Approach

The problem can be solved using Dijkstra’s shortest path algorithm, which is typically used to find the shortest path in a graph with weighted edges. First, you represent the graph using an adjacency list where each node stores the edges (connections to other nodes) and the corresponding weights. Then, you initialize a priority queue to always explore the node with the smallest known path cost first. Starting from the source node, you explore all neighboring nodes, updating the minimum path cost to reach each node. If the destination node can be reached, you return the minimum cost; otherwise, you return “NO”.

Time Complexity

The time complexity is O(M \times log N), where M is the number of edges (triples) and N is the number of nodes. The log factor comes from using the priority queue in Dijkstra’s algorithm.

Space Complexity

The space complexity is O(N + M), where N is the number of nodes and M is the number of edges, as we store the graph in an adjacency list and maintain additional data structures for the algorithm.