# Help with Dijkstra implementation

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?

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.

``````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;
}
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());

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() {
fast();

int T;
cin>>T;
while(T--) {
int n, m, u, v, start, dest, len, sp;
cin>>n>>m>>start>>dest;

for(int i = 0;i<m;i++) {
cin>>u>>v>>len>>sp;
long double t = len / (sp*1.0);
}
dist = vector<long double>(n+1, 1e10);
cout.precision(8);
dist[start] = 0.0;

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!