Yet another shortest path problem

All submissions for this problem are available.
You are given an undirected graph $G$ with $N$ nodes and $M$ edges. Each edge $e$ has a color $c_e$. Define the cost of a path as the number of times the edge color changes. Formally if the path consists of edges $e_1, e_2, \cdots, e_k$ in this order, the cost of the path is the number of $1 \leq i < k$, such that $c_{e_i} \neq c_{e_{i+1}}$. You are given two nodes $s$ and $t$. Find the minimum cost of a path from $s$ to $t$. The path is allowed to have cycles. Please note that there **might** be multiple edges between two nodes but there are no self loops. ###Input:  The first line contains $N$ and $M$, the number of nodes and edges in the graph respectively.  Each of the next $M$ lines contain three integers, $u, v, c$ denoting an undirected edge between $u$ and $v$ having color $c$.  The last line contains two integers, $s$ and $t$. ###Output: Print the minimum cost (as defined in the statement ) of a path from $s$ to $t$ in the graph. ###Constraints  $1 \leq N, M \leq 10^5$  $1 \leq s, t \leq N$  $s \neq t$  $ 1 \leq u, v \leq N$  $ u \neq v$  $1 \leq c \leq 10^5$  There will be at least 1 path from $s$ to $t$ ###Sample Input: ``` 5 5 1 2 1 2 3 2 3 5 3 2 4 2 4 5 2 1 5 ``` ###Sample Output: ``` 1 ``` ###EXPLANATION: We choose the path $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$. The sequence of edge colors is $1, 2, 2$. Clearly we change color only once, and that is the answer.Author:  jtnydv25 
Tags  jtnydv25 
Date Added:  21122018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, kotlin 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions