ompd292's blog

I am not able to find why the code is giving tle for one case??
By ompd292, history, 3 years ago, In English

https://cses.fi/problemset/task/1680/

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<pair<int,int>>adj[n+1];
  for(int i=0;i<m;i++){
    int u,v,wt;
    cin>>u>>v;
    adj[u].push_back({v,1});
  }
  vector<int>dist(n+1,INT_MIN);
  vector<int>par(n+1,-1);
  dist[1]=0;
  priority_queue<pair<int,int>>pq;
  pq.push({0,1});
  while(!pq.empty()){
    int node=pq.top().second;
    int dis=pq.top().first;
    pq.pop();
    for(auto it:adj[node]){
      int adjnode=it.first;
      int wt=it.second;
      
      if(dist[adjnode]<dis+wt){
        dist[adjnode]=dis+wt;
        par[adjnode]=node;
        pq.push({dist[adjnode],adjnode});
      }
    }
  }
  if(dist[n]!=INT_MIN){
  cout<<dist[n]+1<<endl;
  int node=n;
  vector<int>v;
  while(node!=-1){
    v.push_back(node);
    node=par[node];
  }
  reverse(v.begin(),v.end());
  for(int i=0;i<v.size();i++)
  cout<<v[i]<<" ";
  }
  else
  cout<<"IMPOSSIBLE";
  return 0;
}
  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

djikstra for maximum length path is not optimized, since this is a DAG, you'd wanna topo sort it and dp

→ Reply
»
3 years ago, hide # |
← Rev. 5  
Vote: I like it 0 Vote: I do not like it

Note that this problem (CSES: Longest Flight Route) is meant to showcase the technique of Dynamic Programming on a Directed Acyclic Graph (DAG): that is why you are guaranteed "that there are no directed cycles in the flight network". Meanwhile, you apply Dijkstra's Algorithm to this problem. While that is not wrong (Dijkstra's algorithm works on all graphs, directed or undirected, as long as all edge weights are non-negative), it is also not the intended purpose of the problem. Additionally, DP on a DAG yields a lower time complexity than Dijkstra's, as you will see.

As for the reason this program is timing out, it is because you are revisiting nodes in your Dijkstra's loop. Remember that the efficiency of Dijkstra's relies on the fact that once a node has been processed (i.e. once it has been popped from the queue), you should not process it again. Typically, this is ensured by maintaining a visited array which only allows each node in the graph to be processed once, which you may have forgotten. The particular test case that results in a TLE has a configuration of edges where you revisit nodes over and over (which, again, would not happen if you had a visited array), resulting in the TLE.

→ Reply