Planetary Path solution codechef

For Solution

In order to expand its reach to the outer universe and ensure universal peace, the MIB has decided to expand its offices. Namely, it has established its office on NN most important planets in the universe, with the base station on the planet SS. Each office has an intergalactic teleporter that connects it to other planet offices. But the teleporters are bound to a planet’s policy, so you cannot teleport to any planet you wish.

Due to intergalactic feuds, the planets are divided into KK different alliances, numbered 11 through KK. You know for each planet ii, the alliance that it belongs to. In other words, you’re given a sequence A1,A2,…,AnA1,A2,…,An, which says that planet ii belongs to alliance AiAi.

Each planet ii has a policy of teleportation to the planets of other alliances: Planetary Path solution codechef

• Cost to travel from one planet to another is determined by the alliance of the destination planet. More formally, the cost to reach a planet which belongs to alliance jj from planet ii is represented as Ci,jCi,j.
• Intra-alliance travel is free, i.e., if Ai=jAi=j, then Ci,j=0Ci,j=0.
• For a planet ii, there are some forbidden alliances as well. For these alliances, Ci,j=−1Ci,j=−1, given that alliance jj is forbidden to travel from planet ii.

As MIB is bound to follow the intergalactic rules and since they have limited funds (yes, the government is cheap everywhere), they have decided to find the most optimal way to travel to each of the planets from the base station at planet SS. With all other agents busy with their missions, you are assigned the task to find these minimum-cost paths. This is your first task in MIB, so don’t let them down!

Input Format Planetary Path solution codechef

• The first line will consist of three space-separated integers NN, KK, and SS (number of planets, number of alliances, and base planet).
• Second-line will consist of NN space-separated integers representing AiAi, the alliance corresponding to the ithith planet.
• Each of the next NN lines will consist of KK space-separated integers, where the jthjth integer of the ithith line represents Ci,jCi,j, the cost to travel from planet ii to alliance jj.

Output Format

Print NN space separated integers, the ithith integer representing the minimal cost to reach the ithith planet from the base station. For unreachable planets print −1−1.

Constraints Planetary Path solution codechef

• 1≤N≤2∗1041≤N≤2∗104
• 1≤K≤min(N,1000)1≤K≤min(N,1000)
• N∗K≤2∗106N∗K≤2∗106
• 1≤Ai≤K1≤Ai≤K
• −1≤Ci,j≤109−1≤Ci,j≤109

Sample Input 1

``````5 3 4
1 3 1 2 2
0 5 -1
-1 4 0
0 3 -1
4 0 -1
4 0 3
``````

Sample Output 1  Planetary Path solution codechef

``````4 3 4 0 0
``````

Explanation

• As 44 and 55 belong to the same component, the cost of traveling in-between is 00.
• There are multiple shortest paths from 44 to 11. They are: 4→3→1,4→5→3→14→3→1,4→5→3→1, 4→14→1, etc. All of these have equal costs, that is 44.
• Only path from 44 to 22 is 4→5→24→5→2, which costs 33 units.
• Similarly for node 33, the cost is 44 units.