Is this Shortest Path Problem Code: ISITSP

 

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 src, you don't have to include cost of visiting src 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, NM and src, denoting number of nodes, number of edges and source node respectively.
  • Next line has N space separated integers, where ith integer Ai 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 src to every other node. You are required to print this as N space separated integers, with ith integer denoting the answer for visiting Node i from src.

Constraints

  • 1N105
  • 1M106
  • 1src,u,vN
  • 1w109
  • 0Ai109
  • The given graph is connected.

Subtasks

  • 10% points - Graph is a complete graph (KN)
  • 10% points - N1000,M5000
  • 10% points - Ai=0 for all i
  • 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 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

Previous
Next Post »