leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2642.cpp (1041B)

      1 class Graph {
      2     typedef tuple<int, int> Edge;
      3     vector<vector<Edge>> adj;
      4 
      5   public:
      6     Graph(int n, const vector<vector<int>> &edges) : adj(n) {
      7         for (const auto &edge : edges)
      8             addEdge(edge);
      9     }
     10 
     11     void addEdge(const vector<int> edge) { adj[edge[0]].push_back({edge[2], edge[1]}); }
     12 
     13     int shortestPath(int node1, int node2) const {
     14         if (node1 == node2) return 0;
     15         priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
     16         static int seen[101];
     17         memset(seen, 0x00, sizeof(seen));
     18         for (const Edge edge : adj[node1])
     19             pq.push(edge);
     20         while (!pq.empty()) {
     21             while (!pq.empty() && seen[get<1>(pq.top())])
     22                 pq.pop();
     23             if (pq.empty()) break;
     24             const auto [w, n] = pq.top();
     25             pq.pop();
     26             if (n == node2) return w;
     27             seen[n] = true;
     28             for (const auto [w2, n2] : adj[n]) {
     29                 if (!seen[n2]) pq.push({w + w2, n2});
     30             }
     31         }
     32         return -1;
     33     }
     34 };