Help with Dijkstra implementation

This is about this problem.


As far as I can tell, its just dijkstra.
My code is this:
https://www.codechef.com/viewsolution/27906412
I seem to be doing everything correctly, yet only one test case passes. This is getting very annoying.
Can anyone help me out?

I get Access Denied when clicking on this link.

1 Like

I uploaded it on github here,

Someone please help. I have my codechef certcification exam on sunday and I want to know where I’m going wrong. I’ve been trying to find the mistake for 5 hours now.

The only thing that leaps out at me is the line:

n1->timeneeded = n->timeneeded + leng;

which will likely cause problems if n1 is already in the std::priority_queue - when it was added, it used a certain key (its timeneeded) for sorting, and now you have directly modified the value of that key “behind the std::priority_queue's back”, as it were, which will very likely lead to problems when it tries to maintain the “sortedness” invariant as elements are added/ removed.

Maybe try the implementation here?

1 Like

My initial implementation used sets. Same problem with that one too, even though i was deleting and reinserting at every update. :thinking:

using namespace std;

struct node{
    int id;
    bool finished;
    double timeneeded;
    vector<node*> neighbors;
    vector<double> times;
};

node* newNode(int id){
    node* n = new node;
    n->id = id;
    n->finished = false;
    n->timeneeded = (double)LLONG_MAX;
    return n;
}

vector<node*> nodes;

void addEdge(int a, int b, double leng, int sp){
    double dista = leng*1.0/sp;
    nodes[a]->neighbors.push_back(nodes[b]);
    nodes[b]->neighbors.push_back(nodes[a]);
    nodes[a]->times.push_back(dista);
    nodes[b]->times.push_back(dista);
}

struct compare{
    bool operator () (node* a, node* b){
        return (a->timeneeded < b->timeneeded);
    }
};


void solve(){
    int N, M, u, v;
    cin >> N >> M >> u >> v;
    u--;v--;
    nodes.resize(N);
    for(int i = 0; i < N; i++)
        nodes[i] = newNode(i);
    int x,y, sp;
    double leng;
    for(int i = 0; i < M; i++){
        cin >> x >> y >> leng >> sp;
        addEdge(x-1,y-1,leng,sp);
    }
    nodes[u]->timeneeded = 0;
    set<node*,compare> st;
    st.insert(nodes[u]);
    set<node*,compare>::iterator it;
    while(!st.empty()){
        node* n = *st.begin();
        n->finished = true;
        //cout << n->id << " " << n->timeneeded << endl;
        st.erase(st.begin());
        for(int i = 0; i < n->neighbors.size(); i++){
            node* n1 = n->neighbors[i];
            if(n1->finished) continue;
            leng = n->times[i];
            if(n->timeneeded + leng < n1->timeneeded){
                it  = st.find(n1);
                if(it != st.end()) st.erase(it);
                n1->timeneeded = n->timeneeded + leng;
                st.insert(n1);
                //if(n->id == 0) cout << n1->id << " " << n1->timeneeded << endl;
            }
        }
    }
    if(nodes[v]->timeneeded == (double)LLONG_MAX) cout << -1 << endl;
    else cout << nodes[v]->timeneeded << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--)
        solve();
	return 0;
}```

If two nodes have the same timeneeded, a std::set, with your comparison function, will only store one of them.

Try (untested):

struct compare{
    bool operator () (node* a, node* b){
        if (a->timeneeded != b->timeneeded)
            return a->timeneeded < b->timeneeded;
        return a->id < b-> id; // Arbitrary - just want to allow more than one node with the same timeneeded!

    }
};
2 Likes

Thanks! I’ll try this out

1 Like

I have implemented the code using the Dijkstra algorithm with Set

#include <bits/stdc++.h>
using namespace std;

typedef int64_t big;
typedef uint64_t ubig;
typedef long long ll;
typedef unsigned long long ull;

#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front

#define MOD 1000000007
#define PI 3.141592653589793
#define MAXN 1000000000+2

void fast(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); }

vector<long double> dist;
void dij(int start, vector<pair<int, long double>> adj[]) {
    
    set<pair<long double, int>> s;
    s.insert({0.0, start});
    while(!s.empty()) {
        pair<long double, int> p = *(s.begin());
        s.erase(s.begin());
        
        for(auto child : adj[p.second]) {
            if(dist[child.first] > dist[p.second] + child.second) {
                if(dist[child.first] != 1e10) {
                    s.erase(s.find({dist[child.first], child.first}));
                }
                dist[child.first] = dist[p.second] + child.second;
                s.insert({ dist[child.first], child.first });
            }
        }
        
    }
    
}


int main() {
	// your code goes here
	fast();
	
	int T;
	cin>>T;
	while(T--) {
	    int n, m, u, v, start, dest, len, sp;
	    cin>>n>>m>>start>>dest;
	    
	    vector<pair<int, long double>>adj[n+1];
	    for(int i = 0;i<m;i++) {
	        cin>>u>>v>>len>>sp;
	        long double t = len / (sp*1.0);
	        adj[u].push_back(make_pair(v, t));
	        adj[v].push_back(make_pair(u, t));
	    }
	    dist = vector<long double>(n+1, 1e10);
	    cout.precision(8);
	    dist[start] = 0.0;
	    
	    dij(start, adj);
	    if(dist[dest] == 1e10)
	        cout<<"-1\n";
        else
            cout<<fixed<<dist[dest]<<"\n";
	    
	}
	
	return 0;
}




1 Like

Seems good! Eliminates the need to define a compare function! Thanks!