Need Help in this Graph problem !!!!

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

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

4 months 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

4 months ago, # ^ |

← Rev. 2 →

Sorry I did not get this line.

Update : Got it Thank You.

Roronoa__Zoro's blog