3977. Minimum Time to Reach Target With Limited Power

You are given a directed weighted graph with n nodes labeled from 0 to n - 1.

The graph is represented by a 2D integer array edges, where edges[i] = [u_i, v_i, t_i] indicates a directed edge from node u_i to node v_i that takes t_i seconds to traverse.

You are also given an integer power representing the initial available power, and an integer array cost of length n, where cost[u] represents the power required to forward the signal from node u through any one of its outgoing edges.

You are given two integers source and target.

The signal starts at source at time 0 with power units of power and follows these rules:

• The signal may traverse a directed edge from node u only if the remaining power is at least cost[u].
• No power is consumed when the signal arrives at a node, unless it later leaves that node by traversing another edge.
• When the signal is forwarded from node u, the remaining power is decreased by cost[u] units.
• Traversing an edge edges[i] = [u_i, v_i, t_i] increases the total time by t_i seconds.

Return an integer array answer of size 2, where:

• answer[0] is the minimum time required for the signal to reach node target.
• answer[1] is the maximum remaining power among all paths that achieve answer[0].

If the signal cannot reach target, return [-1, -1].

class Solution {
public:
    vector<long long> minTimeMaxPower(int n, vector<vector<int>>& edges, int power, vector<int>& cost, int source, int target) {
        vector<vector<pair<int,int>>> adj(n);
        for(auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            adj[u].push_back({v,w});
        }
        vector<vector<long long>> times(n, vector<long long>(power + 1, LLONG_MAX));

        priority_queue<array<long long,3>,vector<array<long long,3>>, greater<>> q;
        auto push = [&](long long u, long long t, long long p) {
            if(p > power) return;
            if(times[u][p] <= t) return;
            times[u][p] = t;
            q.push({t,p,u});
        };
        push(source,0,0);
        while(q.size()) {
            auto [time, pow, u] = q.top(); q.pop();
            if(times[u][pow] != time) continue;
            for(auto& [v,w] : adj[u]) {
                push(v,time + w, pow + cost[u]);
            }
        }
        vector<long long> res{LLONG_MAX, LLONG_MAX};
        for(int pow = 0; pow <= power; pow++) {
            if(times[target][pow] == LLONG_MAX) continue;
            vector<long long> now{times[target][pow], power - pow};
            if(res[0] == now[0]) res = max(res, now);
            else res = min(res, now);
        }
        if(res[0] == LLONG_MAX) res = {-1,-1};
        return res;
    }
};