• Recently I came across a new idea to solve graph-related problems using segment trees, I would like to discuss the same with a problem.

Problem:

Given a graph G with N nodes and many edges (around $$$O(N^2)$$$), the goal is to perform Dijkstra algorithm on this dense graph and find out the shortest path from node 1 to all other nodes.

The edges are given in a compressed format. The input follows $$$M$$$ lines. Each of the M lines consists of 4 integers U Lx Rx C meaning there are edges from node U to all other nodes in range [Lx , Rx] with cost C.

Example: N = 6
U = 1
Lx = 3
Rx = 5
C = 2