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, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 