PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY
PREREQUISITES:
Dijkstra’s Algorithm, Graph Theory
PROBLEM:
There’s a weighted graph with n vertices and m edges. Additionally, each edge has a color. It is known the cost to go from one edge of color i to one edge of color j for all possible (i, j). Find the shortest path from vertex s to all other vertices.
EXPLANATION:
The first subtask can be solved using BFS, since the graph is unweighted and the colors of each edge is the same. Similarly, subtask 2 can be solved with a direct application of Dijkstra’s Algorithm.
The last subtask requires a small trick. We construct a new graph where each vertex is split into k different vertices. In the new graph, the vertex (i, j) denotes that we are at vertex i and the color of the last edge we used is color j. Now, we can apply Dijkstra’s Algorithm on this new graph and get the correct answer.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.