leetcode

Solution to some Leetcode problems written in C++

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

2699.cpp (1987B)

0 class Solution { 1 using edge_t = pair<int, int>; 2 using adj_t = vector<vector<edge_t>>; 3 4 void dijkstra(const adj_t &adj, vector<vector<int>> &edges, vector<vector<int>> &dist, int src, int diff, 5 int run) { 6 int n = adj.size(); 7 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; 8 9 dist[src][run] = 0; 10 pq.emplace(0, src); 11 while (!pq.empty()) { 12 auto [currentdist, currentNode] = pq.top(); 13 pq.pop(); 14 15 if (currentdist > dist[currentNode][run]) continue; 16 for (auto &[next, idx] : adj[currentNode]) { 17 int w = edges[idx][2]; 18 19 if (w == -1) w = 1; 20 21 if (run == 1 && edges[idx][2] == -1) { 22 int nw = diff + dist[next][0] - dist[currentNode][1]; 23 if (nw > w) { 24 edges[idx][2] = w = nw; 25 } 26 } 27 28 if (dist[next][run] > dist[currentNode][run] + w) { 29 dist[next][run] = dist[currentNode][run] + w; 30 pq.emplace(dist[next][run], next); 31 } 32 } 33 } 34 } 35 36 public: 37 vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>> &edges, int src, int dest, int tgt) { 38 vector<vector<pair<int, int>>> adj(n); 39 for (int i = 0; i < edges.size(); i++) { 40 int a = edges[i][0], b = edges[i][1]; 41 adj[a].emplace_back(b, i); 42 adj[b].emplace_back(a, i); 43 } 44 45 vector<vector<int>> dist(n, vector<int>(2, INT_MAX)); 46 dist[src][0] = dist[src][1] = 0; 47 48 dijkstra(adj, edges, dist, src, 0, 0); 49 int diff = tgt - dist[dest][0]; 50 if (diff < 0) return {}; 51 52 dijkstra(adj, edges, dist, src, diff, 1); 53 if (dist[dest][1] < tgt) return {}; 54 55 for (auto &edge : edges) { 56 if (edge[2] == -1) edge[2] = 1; 57 } 58 return edges; 59 } 60 };