# C++ Dijkstra Algo 458ms with priority_queue

• Dijkstra algorithm apparently overkills this problem. A BFS is more straightforward. But I share my accepted solution as below for reference.
I implement priority_queue as a heap to facilitate fast access of the next vertex with smallest distance.

Question:
Implementing a heap in C++ always bothers me a little. What choices other than priority_queue do I have?

``````class mycompare
{
public:
bool operator() (pair<int, string> & p1, pair<int, string> & p2)
{
return p1.first > p2.first;
}
};

class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wl) {
wl.push_back(beginWord);
unordered_map<string, set<string>> m;    // Adjacency list
unordered_map<string, int> dis;    // Latest distances of all vertices
priority_queue<pair<int, string>, vector<pair<int, string>>, mycompare> pq;    // Use priority queue as a heap to retrieve the next vertex with smallest distance.
unordered_set<string> words;    // The set of vertices which have not been visited
for (int i = 0; i < wl.size() - 1; i++) {
dis[wl[i]] = INT_MAX;
pair<int, string> temp (INT_MAX, wl[i]);    // Set default distances of all vertices, other than beginWord, as infinite.
pq.push(temp);
words.insert(wl[i]);
for (int j = i + 1; j < wl.size(); j++) {
if (diff_by_one(wl[i], wl[j])) {
m[wl[i]].insert(wl[j]);
m[wl[j]].insert(wl[i]);
}
}
}
dis[beginWord] = 1;
pair<int, string> temp (1, beginWord);
pq.push(temp);
words.erase(beginWord);

while (!words.empty()) {
string u = pq.top().second;
if (u == endWord) {
if (dis[u] != INT_MAX) return dis[u];
else return 0;
}
pq.pop();
words.erase(u);
for (auto & v : m[u]) {
if (words.find(v) != words.end()) {
if (dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1;
pair<int, string> temp (dis[v], v);
pq.push(temp);
}
}
}
}
return 0;
}
private:
bool diff_by_one(string& s1, string& s2) {
int count = 0;
for (int i = 0; i < s1.size(); i++) {
if (s1[i] != s2[i]) count ++;
if (count > 1) return false;
}
return true;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.