I was solving this problem on the CSES Problemset [Longest Flight Route](https://cses.fi/problemset/task/1680/).↵
↵
<spoiler summary="Here is my code">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
signed main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
int N,M; cin >> N >> M;↵
vector<vector<int>> graph(N);↵
vector<int> D(N, 0), parent(N, 0);↵
for(int i = 0; i < M; i++){↵
int u,v; cin >> u >> v;↵
graph[u - 1].emplace_back(v - 1);↵
}↵
queue<int> q;↵
q.push(0);↵
D[0] = 1;↵
parent[0] = -1;↵
while(!q.empty()){↵
int node = q.front();↵
q.pop();↵
for(int v : graph[node]){↵
if(D[v] < D[node] + 1){↵
D[v] = D[node] + 1;↵
parent[v] = node;↵
q.push(v);↵
}↵
}↵
}↵
if(D[N - 1] == 0){↵
cout << "IMPOSSIBLE\n";↵
return 0;↵
}↵
cout << D[N - 1] << '\n';↵
vector<int> answer;↵
int node = N - 1;↵
while(node != -1){↵
answer.emplace_back(node + 1);↵
node = parent[node];↵
}↵
reverse(answer.begin(), answer.end());↵
for(int e : answer)↵
cout << e << ' ';↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
The code is getting Accepted in all but 2 testcases(TLE in those 2) .↵
↵
I cannot debug with those testcases since they are HUGE. ↵
↵
I reckon that the problem is in my BFS Code but I can't seem to find why it would go in an infinity loop.↵
↵
If anyone could provide a testcase or something it would be incredibly helpful.↵
↵
Thanks.
↵
<spoiler summary="Here is my code">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
signed main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
int N,M; cin >> N >> M;↵
vector<vector<int>> graph(N);↵
vector<int> D(N, 0), parent(N, 0);↵
for(int i = 0; i < M; i++){↵
int u,v; cin >> u >> v;↵
graph[u - 1].emplace_back(v - 1);↵
}↵
queue<int> q;↵
q.push(0);↵
D[0] = 1;↵
parent[0] = -1;↵
while(!q.empty()){↵
int node = q.front();↵
q.pop();↵
for(int v : graph[node]){↵
if(D[v] < D[node] + 1){↵
D[v] = D[node] + 1;↵
parent[v] = node;↵
q.push(v);↵
}↵
}↵
}↵
if(D[N - 1] == 0){↵
cout << "IMPOSSIBLE\n";↵
return 0;↵
}↵
cout << D[N - 1] << '\n';↵
vector<int> answer;↵
int node = N - 1;↵
while(node != -1){↵
answer.emplace_back(node + 1);↵
node = parent[node];↵
}↵
reverse(answer.begin(), answer.end());↵
for(int e : answer)↵
cout << e << ' ';↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
The code is getting Accepted in all but 2 testcases(TLE in those 2) .↵
↵
I cannot debug with those testcases since they are HUGE.
↵
I reckon that the problem is in my BFS Code but I can't seem to find why it would go in an infinity loop.↵
↵
If anyone could provide a testcase or something it would be incredibly helpful.↵
↵
Thanks.
