Need Help in this Graph problem !!!!

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	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	157
8	TheScrasse	154
9	Dominater069	153
9	nor	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

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