题解 | #旅行Ⅰ#

// 什么压行狂魔（
class Solution {
public:
    using pii = pair<int,int>;
    vector<int> ed[100010];
    int d[100010],ans=0;
    int Travel(int N, int V, vector<int>& A, vector<Point>& list) {
        for(auto [x,y]:list)  ed[x].push_back(y),d[y]++;
        auto cmp = [&](pii a,pii b) -> bool{
            if(a.first == b.first) return a.second < b.second;
            else return a.first < b.first;
        };
        priority_queue<pii,vector<pii>,decltype(cmp)> pq(cmp);
        for(int i=1;i<=N;i++) if(!d[i]) pq.push({i,A[i]});
        while(!pq.empty())
        {
            auto [x,y] = pq.top(); pq.pop();
            if(V<y) break; V-=y;
            ans++;
            for(auto v:ed[x]) if(--d[v] == 0)  pq.push({v,A[v]});
        }
        return ans;
    }
};