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.
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?
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;
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!
}
};
Thanks! I’ll try this out
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;
}
Seems good! Eliminates the need to define a compare function! Thanks!