题解 | #旅行Ⅰ#

class Solution {
public:
    struct status {
        int city; // 从0到n-1
        int cost; // 花费
        bool operator < (const status& a) const { // 为优先队列制定规则
            if (cost != a.cost) // 先看消费，选消费低的
                return cost > a.cost;
            else // 消费一样选城市编号小的
                return city > a.city;
        }
    };
    int Travel(int N, int V, vector<int>& A, vector<Point>& list) {
        // 用来存储一个城市到其他城市的图，用于拓扑排序
        unordered_map<int,unordered_set<int>> graph; 
        vector<int> inDgrees(N, 0); // 存储每个城市结点的入度，没有强迫症要求的入度为0
        priority_queue<status> q;
        for (auto& point: list) {
            graph[point.x-1].insert(point.y-1);
            inDgrees[point.y-1]++;
        }
        for (int i = 0; i < N; i++) { // 创建完图后，把入度为0的结点放入优先队列
            if (inDgrees[i] == 0) {
                q.push({i,A[i]});
            }
        }
        int costSum = 0, cnt = 0;
        while (!q.empty()) {
            status top = q.top();
            q.pop();
            costSum += top.cost;
            if (costSum > V) // 本次消费会炸，只能返回上次的城市数cnt
                break;
            cnt++;
            for (auto i: graph[top.city]) { // 讲当前弹出的城市与其他城市的连接断开，即其他城市入度-1
                inDgrees[i]--;
                if (inDgrees[i] == 0)
                    q.push({i,A[i]});
            }
        }
        return cnt;
    }
};