manijuana's blog

CSES Shortest Routes 1
By manijuana, history, 5 years ago, In English

I'm having trouble implementing a typical dijikstra problem (this one). I'm having a TLE verdict in the last subtask. My submission can be found here. I'm using a set to store the nodes and having a compare function which sorts on the basis of the shortest distances stored in vector d. Everytime a relaxation is encountered, it removes the node, relaxes and changes d[] for that node and enters it again into the set. Can anyone help me get rid of this TLE and tell me why I'm getting one? Thanks in advance.

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Use priority_queue instead, it's faster and more useful. A nice implementation can be found at https://cp-algorithms.com/graph/dijkstra_sparse.html

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I implemented this version of dijikstra from this source only. I didn't use a priority queue cause I wanted to write a shorter code without all those pairs using a set which I'm more comfortable with. But I'm doing something wrong and I can't figure out what :(

    → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

https://codeforces.net/blog/entry/70237

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks a lot I didn't know this at all. I'll remember this now onward. After I fixed that compare function to return false when elements are equal though the last subtask is accepted it shows WA on some other ones which was not the case before. I'm confused and pretty sure the problem is with my comp function but now what is it? Thanks in advance.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The reason why I'm so sure that my comparator has a problem is because I submitted the solution with a set of pair of shortest distance and node, and it works fine.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did you just return false when elements are equal or did you change <= into <? Because you should do the latter.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I changed <= to < here is the code but it's getting WA verdict. Whereas when I use this code I get an AC. I can't figure out what's wrong with using a custom made comparator versus the inbuilt one in set.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why i am getting tle for two test cases below is the code could someone tell me what to do

void solve(vector<node>adj[],int n) {
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
    vector<ll>dist(n,LLONG_MAX);
    dist[1] = 0;
    pq.push({0,1});

    while(not pq.empty()) {
        ll u =pq.top().second;
        pq.pop();
        
        for(auto i:adj[u]) {
            if(i.des == 1) continue;
            ll v = i.des;
            ll w = i.weight;
            if(dist[u]+w <dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v],v});
            }
        }
    }

    loop(i,1,n) {
        cout<<dist[i]<<" ";
    }
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't visit already visited nodes,use an array of mark[],it should work.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But suppose you get shortest path from another node , so if mark it visited then there may be possibility i missed some small distance then another route

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        ll u =pq.top().second;
    pq.pop();
     if(mark[u]==1)
        continue;
    mark[u]=1.

        something like this.

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

use visited array to ensure not visit same node again which is already minimum.

→ Reply