C++ Dijkstra Algo 458ms with priority_queue


  • 0
    C

    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;
        }
    };
    

Log in to reply
 

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