text: * The robot uses an edge of weight 4.* The robot reaches the node 4, with 12 - 4 = 8 energy points.* The robot uses an edge of weight 8.* The robot reaches the node 1 with 8 - 8 = 0 energy points.* The robot is on a central, so its battery is recharged.He has now c = 12 energy points.* The robot uses an edge of weight 2.* The robot is on the node 5, with 12 - 2 = 10 energy points.* The robot uses an edge of weight 3.* The robot is on the node 7, with 10 - 3 = 7 energy points.* The robot uses an edge of weight 2.* The robot is on the node 3, with 7 - 2 = 5 energy points.* The robot is on a central, so its battery is recharged.He has now c = 12 energy points.* End of the simulation.Note that if value of c was lower than 12, we would have less than 8 energy points on node 4, and we would be unable to use the edge 4 ↔ 1 of weight 8.Hence 12 is the minimum capacity required to acheive the mission.— The graph of the second example is described here (centrals are red nodes): <image> The robot can acheive the mission (3, 1) with a battery of capacity c = 38, using the path 3 → 9 → 8 → 7 → 2 → 7 → 6 → 5 → 4 → 1 The robot can acheive the mission (2, 3) with a battery of capacity c = 15, using the path 2 → 7 → 8 → 9 → 3 # Solution #include <bits/stdc++.h> using namespace std; struct Edge { int x, y; long long val; } e[3 * 100055]; bool cmp(Edge x1, Edge x2) { return x1.val < x2.val; } int head[100055], to[6 * 100055], nex[6 * 100055]; long long w[6 * 100055]; int edge; inline void addEdge(int x, int y, long long z) { to[++edge] = y, w[edge] = z, nex[edge] = head[x], head[x] = edge; to[++edge] = x, w[edge] = z, nex[edge] = head[y], head[y] = edge; } int n, m, k, q; void init() { for (int i = 1; i <= n; i++) head[i] = 0; edge = 0; } bool vis[100055]; long long d[100055]; struct node { int x; long long val; node(int x, long long val) : x(x), val(val) {} friend bool operator<(node x1, node x2) { return x1.val > x2.