Need Help in this Graph problem !!!!

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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

3 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

3 months ago, # ^ |

← Rev. 2 →

Sorry I did not get this line.

Update : Got it Thank You.

Roronoa__Zoro's blog