leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2642.cpp (1041B)

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