There are n towns numbered 1 to n, and m roads connecting them. Arrays a and b are given such that road i connects towns a[i] and b[i]. Your task is to return an array of size m whose i-th element denotes the least number of roads that would be used in traveling from town 1 to town n when the i-th road cannot be used in the traversal. Return -1 as the i-th element if it is impossible to travel from town 1 to town n without using the i-th road. Graph is Undirected and all pairs (a[i] , b[i]) are distinct.
$$$Constraints$$$
$$$2 \le n \le 300$$$
$$$1 \le m \le n*(n-1)$$$
$$$ a[i] != b[i] $$$
$$$ 1 \le a[i] , b[i] \le n$$$
I tried this code but the time complexity will be $$$O(m{^2})$$$.
code
Problem : Find the shortest path from 1 to n, when the i-th edge can't be used.
Solution : Find the shortest path from 1 to n. If the edge we are removing does not belong to this path then the answer is just the distance (length of the shortest path).
If it does, then just do the naive check (remove the edge and find the shortest distance). Since there are only O(n) edges in the path, we do the naive algorithm only O(n) times.
Time Complexity : O(n * (n + m))
Sorry I did not get this line.
If it does, then just do the naive check (remove the edge and find the shortest distance). Since there are only O(n) edges in the path, we do the naive algorithm only O(n) times.
Update : Got it Thank You.