Блог пользователя manijuana

Автор manijuana, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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]<<" ";
    }
}

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ll u =pq.top().second;
            pq.pop();
             if(mark[u]==1)
                continue;
            mark[u]=1.

        something like this.

»
18 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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