Dijkstra's algorithm: Memory limit exceeded

Revision en1, by aayuagarwal, 2020-05-03 15:05:02

In the Problem 20C "Memory limit exceeded" on testcase 31. Can someone please suggest, how to reduce space in this following 78886598

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
     cin>>n>>m;
    long long int dist[n];
    int from[n];
    for(int i = 0 ; i<n ; i++){
        dist[i] = INT_MAX;
        from[i] = -1;
    }

    vector<vector<pair<int,int>>> g(n);
    set<pair<int,int>> q;
    for(int i = 0 ; i<m ; i++){
        int u,v,d;
        cin>>u>>v>>d;
        g[u-1].push_back(make_pair(v,d));
        g[v-1].push_back(make_pair(u,d));
    }
    dist[0] = 0;
    from[0] = 1;
    pair<int,int> vov = make_pair(0,1);
    q.insert(vov);
    while(!q.empty()){
        pair<int,int> p = *q.begin();
        q.erase(p);
        int u = p.second;
        dist[u-1] = p.first;
        for(int i = 0 ; i<g[u-1].size() ; i++){
            if(dist[g[u-1][i].first-1] > p.first + g[u-1][i].second){
                pair<int,int> vo = make_pair(p.first + g[u-1][i].second,g[u-1][i].first);
                q.insert(vo);
                pair<int,int> re= make_pair(dist[g[u-1][i].first-1],g[u-1][i].first);
                q.erase(re);
                dist[g[u-1][i].first-1] = p.first + g[u-1][i].second;
                from[g[u-1][i].first-1] = u;
            }
        }
    }
    int i = n-1;
    if(from[i] == -1) cout<<-1<<endl;
        else{
            vector<int > s;
            s.push_back(n);
            while(i>0){
                 s.push_back(from[i]);
                i = from[i]-1;
            }
            for(int j = s.size()-1 ; j>=0 ; j--){
                cout<<s[j]<<" ";
            }
        }
}

Tags djikstra

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English aayuagarwal 2020-05-03 15:05:02 1828 Initial revision (published)