2737. Find the Closest Marked Node

You are given a positive integer n which is the number of nodes of a 0-indexed directed weighted graph and a 0-indexed 2D array edges where edges[i] = [ui, vi, wi] indicates that there is an edge from node ui to node vi with weight wi.

You are also given a node s and a node array marked; your task is to find the minimum distance from s to any of the nodes in marked.

Return an integer denoting the minimum distance from s to any node in marked or -1 if there are no paths from s to any of the marked nodes.

c++

class Solution {
public:
    int minimumDistance(int n, vector<vector<int>>& edges, int s, vector<int>& marked) {
        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<long long> cost(n, INT_MAX);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
        auto push = [&](int u, int c) {
            if(cost[u] > c) {
                cost[u] = c;
                q.push({c,u});
            }
        };
        push(s,0);
        long long res = INT_MAX;
        unordered_set<int> us(begin(marked), end(marked));
        while(q.size()) {
            auto [c,u] = q.top(); q.pop();
            if(cost[u] != c) continue;
            if(us.count(u)) res = min(res, cost[u]);
            for(auto& [v,w] : adj[u]) {
                push(v,c + w);
            }
        }
        return res >= INT_MAX ? -1 : res;
    }
};