Is this Shortest Path Problem Code: ISITSP ~ Multiplex Coder

Statement:

In a far away Galaxy of Tilky Way, there was a planet Tarth where the sport of Tompetitive Toding was very popular. According to legends, there lived a setter who loved giving impossible variants of Shortest Path Algorithms.

You are given an undirected, weighted graph $G$ with $N$ nodes and $M$ edges. The nodes are labelled from $1$ to $N$ . This graph is different from normal graphs, because in this graph, both - nodes and edges - have a cost or weight associated with them. There is a cost to travel an edge, and also a cost to arrive at a node. You are required to find the cost of the cheapest path from Node src to every other node in the graph.

Note- The cost of a path is sum of cost of all edges and all nodes visited in the path, as inferred from the statement. Since you already start at $s r c$ , you don't have to include cost of visiting $s r c$ in the answer. Refer to sample for more clarity.

Note: The graph could contain multi-edges and self-loops.

Input:

The first line has $3$ integers, $N$ , $M$ and $s r c$ , denoting number of nodes, number of edges and source node respectively.
Next line has $N$ space separated integers, where $i^{'} t h$ integer $A_{i}$ denotes the cost of arriving at that node.
Next $M$ lines have $3$ integers, $u v w$ , denoting that there is an edge between nodes $u$ and $v$ with weight $w$ .

Output:

Print the minimum cost to go from $s r c$ to every other node. You are required to print this as $N$ space separated integers, with $i^{'} t h$ integer denoting the answer for visiting Node $i$ from $s r c$ .

Constraints

$1 \leq N \leq 10^{5}$
$1 \leq M \leq 10^{6}$
$1 \leq s r c, u, v \leq N$
$1 \leq w \leq 10^{9}$
$0 \leq A_{i} \leq 10^{9}$
The given graph is connected.

Subtasks

10% points - Graph is a complete graph $(K_{N})$
10% points - $N \leq 1000, M \leq 5000$
10% points - $A_{i} = 0$ for all $i$
70% points - Original Constraints

Sample Input:

Sample Output:

0 11 1001

EXPLANATION:

The cost to go from Node $1$ to itself is $0$ (you start from src and hence its already visited for no cost). To go to Node $2$ , it will use the edge of weight $10$ . Also, Node $2$ has a cost of $1$ for visiting, hence total cost is $11$ . Similarly, we can visit Node $3$ directly from Node $1$ for a cost of $1000 + 1 = 1001$ .

Click here