题解 | #旅行Ⅰ#

 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
    //重写仿函数，满足优先队列的top是花费最小(花费相同，编号最小)
    struct cmp
    {
        bool operator()(pair<int,int>&a, pair<int,int>&b)
        {
            if(a.second == b.second) return a.first > b.first;
            return a.second > b.second;
        }
    };
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型vector A
     * @param list Point类vector List
     * @return int整型
     */
    int Travel(int N, int V, vector<int>& A, vector<Point>& list) {
        // write code here
        //degree[i]代表要去i城市前还需要去的城市数目
        vector<int> degree(N, 0);
        //建立邻接矩阵
        //maps[i]中的元素是在去过i城市才能去的城市
        vector<vector<int>> maps(N);
        //初始化degree和邻接矩阵
        for(auto ele : list)
        {
            //注意list中的元素需要减一来对应数组真实下标
            ++ degree[ele.y-1];
            maps[ele.x-1].push_back(ele.y-1);
        }
        int res = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> q;
        //出度为0的入优先队列
        for(int i=0; i<N; ++i)
        {
            if(degree[i] == 0) q.push({i, A[i]});
        }
        
        while(!q.empty())
        {
            pair<int,int> cur = q.top();
            q.pop();
            //钱不够，直接return
            if(V < cur.second) return res;
            else{
                //当前城市可以去，更新res，剩余钱V
                //同时更新在去过城市cur.first后才能去的城市的出度
                //如果有出度为0的，加入优先队列
                ++ res;
                V -= cur.second;
                for(auto ele : maps[cur.first])
                {
                    if(--degree[ele] == 0)
                        q.push({ele, A[ele]});
                }
            }
        }
        return res;
    }
};