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