Need Help in this Graph problem !!!!

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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

5 months ago, # ^ |

← Rev. 2 →

Sorry I did not get this line.

Update : Got it Thank You.

Roronoa__Zoro's blog