Not able to figure out why my code is not optimal
Difference between en1 and en2, changed 7 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English arnav2004 2022-01-13 16:42:43 7 (published)
en1 English arnav2004 2022-01-13 16:39:53 1489 Initial revision (saved to drafts)