### vaibhavmisra's blog

By vaibhavmisra, history, 6 weeks ago, Hello everyone, I have been trying to find shortest path using dijkstra with set by storing indices instead of index-distance pairs with the help of a custom comparator. It is failing on a very large test case and I am having a difficult time debugging it. Where am I doing wrong? Any type of hint would be appreciated.

vector<ll> d;

struct comp {
bool operator()(const int& a, const int& b) const {
return d[a] < d[b];
}
};

void solve() {
int n, m; cin >> n >> m;
vector<vector<pii>> graph(n + 1);
set<int, comp> q;
rep(m) {
int a, b, c; cin >> a >> b >> c;
graph[a].push_back(make_pair(b, c));
graph[b].push_back(make_pair(a, c));
}
vector<int> p(n + 1, -1);
d.resize(n + 1, LLONG_MAX);
d = 0;
q.insert(1);
while(!q.empty()) {
int node = *q.begin();
q.erase(q.begin());
}
}
}
if(d[n] == LLONG_MAX) cout << -1 << endl;
else {
vector<int> path;
while(n != -1) {
path.push_back(n);
n = p[n];
}
rep(path.size()) cout << path[path.size() - i - 1] << ' '; cout << endl;
}
}  Comments (3)
 » Check the following priority-queue based solution.158638653
 » You have a problem in your custom comparator. Change it to spoilerstruct comp { bool operator()(const int & a, const int & b) const { if (d[a] == d[b]) { return a < b; } return d[a] < d[b]; } }; Basically when you have two distinct nodes sharing the same distance only one of them can exist in the set at a given time using your old comparator implementation.
•  » » Thank you! I found the reason.