Need Help in this Graph problem !!!!

#	User	Rating
1	tourist	3947
2	ecnerwala	3654
3	jiangly	3627
4	jqdai0815	3620
5	orzdevinwang	3612
6	Benq	3586
7	Radewoosh	3582
8	Geothermal	3569
8	cnnfls_csy	3569
10	ksun48	3474

#	User	Contrib.
1	awoo	163
2	maomao90	160
3	adamant	156
4	atcoder_official	155
5	maroonrk	152
6	-is-this-fft-	148
6	SecondThread	148
8	Petr	147
9	nor	145
10	cry	144

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

int f(int ind , int n , vector&a , vector&b) {

vector<int>adj[n + 1];

int m = a.size();

for (int i = 0 ; i < m ; i++) {

    if (i == ind)continue;

    adj[a[i]].push_back(b[i]);

    adj[b[i]].push_back(a[i]);

}

vector<int>dist(n + 1 , 1e9);

dist[1] = 0;

queue<int> q;

q.push(1);

while (!q.empty()) {

    int u = q.front();

    q.pop();

    for (auto v : adj[u]) {

       if (dist[v] > 1 + dist[u]) {

         dist[v] = 1 + dist[u];

         q.push(v);

       }

    }

}

return dist[n] == 1e9 ? -1 : dist[n];

}

vector townTravel(int n , vector&a , vector& b) {

int m = a.size();

vector<int> ans;

for (int i = 0 ; i < m ; i++) {

    int num = f(i , n , a , b);

    ans.push_back(num);

}

return ans;

}

Comments (2)

Write comment?

Ghulam_Junaid

5 hours ago, # |

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))

→ Reply

Roronoa__Zoro

5 hours ago, # ^ |

← Rev. 2 →

Sorry I did not get this line.

Update : Got it Thank You.

Roronoa__Zoro's blog