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 with nodes and edges. The nodes are labelled from to . 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 , you don't have to include cost of visiting in the answer. Refer to sample for more clarity.
Note: The graph could contain multi-edges and self-loops.
Input:
- The first line has integers, , and , denoting number of nodes, number of edges and source node respectively.
- Next line has space separated integers, where integer denotes the cost of arriving at that node.
- Next lines have integers, , denoting that there is an edge between nodes and with weight .
Output:
Print the minimum cost to go from to every other node. You are required to print this as space separated integers, with integer denoting the answer for visiting Node from .
Constraints
- The given graph is connected.
Subtasks
- 10% points - Graph is a complete graph
- 10% points -
- 10% points - for all
- 70% points - Original Constraints
Sample Input:
3 3 1
1 1 1000
1 2 10
1 3 1
3 2 1
Sample Output:
0 11 1001
EXPLANATION:
The cost to go from Node to itself is (you start from src
and hence its already visited for no cost). To go to Node , it will use the edge of weight . Also, Node has a cost of for visiting, hence total cost is . Similarly, we can visit Node directly from Node for a cost of .
ConversionConversion EmoticonEmoticon