### 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.