leetcode

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