Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

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

CSES Shortest Routes 1
Автор manijuana, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +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

→ Ответить
  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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 :(

    → Ответить
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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]<<" ";
    }
}
→ Ответить
  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    22 месяца назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится 
    void solve(){
    ll n,m; cin>>n>>m;
    vector<pii>adj[n+1];
    fri(i,1,m){
        ll a,b,c; cin>>a>>b>>c;
        adj[a].pb({b,c});
    }
    vector<ll>dis(n+1,1e18);
    priority_queue<pii, vector<pii>, greater<pii>>pq;
    pq.push({0,1}); dis[1]=0;
    while(!pq.empty()){
        auto cur=pq.top(); pq.pop();
        ll node=cur.second;
        ll node_dis=cur.first;
        
        if(node_dis>dis[node])continue;

        for(auto child:adj[node]){
            ll child_node=child.first;
            ll child_dis=child.second;
            if(node_dis+child_dis<dis[child_node]){
                dis[child_node]=node_dis+child_dis;
                pq.push({dis[child_node],child_node});
            }
        }
    }

    for(ll i=1; i<=n; i++){
        cout<<dis[i]<<" ";
    }cout<<endl;
}
    → Ответить
    • »
      »
      »
      20 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      can you please tell what is wrong in this code;
      ~~~~~~~~~~~~~

      include<bits/stdc++.h>

      using namespace std;

      define ll long long int

      void solve(){ ll n; ll m; cin>>n>>m; vector<vector<pair<ll,ll>>>adi(n+1); vectorvis(n+1,false); vectordist(n+1,INT32_MAX); dist[1]=0; for (ll i = 0; i < m; i++) { ll a,b,c; cin>>a>>b>>c; adi[a].push_back({b,c}); }

      priority_queue<pair<ll,ll>, vector<pair<ll,ll>> , greater<pair<ll,ll>> >pq;

      pq.push({0,1});

      while(pq.size()!=0){ ll min_val = pq.top().first; ll idx = pq.top().second; // cout<<min_val<<" "<<idx<<"\n"; pq.pop(); vis[idx] = true; if(dist[idx] < min_val)continue;

      for (auto to : adi[idx]) {
      if(vis[to.first])continue; ll new_dis = to.second + dist[idx]; if(new_dis < dist[to.first]) dist[to.first]=new_dis; pq.push({new_dis,to.first}); }

      } for (ll i = 1; i <n+1; i++) { cout<<dist[i]<<" ";

      }

      }

      int main(){

      int t; t=1; while(t--){ // solve(); ; } } ~~~~~~~~~

      → Ответить
»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить