题解 |优先队列+拓扑排序

题目分析

1. 有N个城市，每个城市有编号（1~N）和消费额
2. 所去城市有部分一对一先后顺序（设计拓扑排序）
3. 在满足强迫症后的选择策略：（优先队列）
   • 1. 先考虑消费低的城市
   • 2. 再考虑城市编号更小的城市

我们可以把城市先后顺序用哈希表映射到集合来记录，表示要先去一个城市，才能去该城市对应的集合中的城市。 用inDegree数组存储每个城市的入度，入度为0的入优先队列，表示可以满足强迫症要求。 但是出队列要有顺序，我们自己制定优先队列里元素的大小比较规则： 用结构体记录城市的编号和消费额； 消费额小的优先级大，消费额相同则编号小的优先级大

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
struct City {
    int num;
    int cost;
};
struct cmp {
    bool operator() (City& a, City& b) {
        if (a.cost != b.cost)
            return a.cost > b.cost;
        else
            return a.num > b.num;
    }
};
class Solution {
public:
    int Travel(int N, int V, vector<int>& A, vector<Point>& list) {
        // write code here
        vector<City> citys(N+1); // 入队备用记录
        vector<int> inDegree(N+1, 0); // 判断能否入队
        for (int i = 1; i <= N; i++) { // 优先队列所比较的整体元素
            citys[i].num = i; 
            citys[i].cost = A[i-1];
        }
        unordered_map<int, unordered_set<int> > graph; // 记录先后顺序
        for (auto p: list) {
            graph[p.x].insert(p.y);
            inDegree[p.y] ++;
        }
        priority_queue<City, vector<City>, cmp> prty;
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                prty.push(citys[i]);
            }
        }
        int v_sum = 0;
        int cnt = 0;
        while (!prty.empty()) {
            City city = prty.top();
            prty.pop();
            v_sum += city.cost;
            if (v_sum > V)
                break;
            cnt++;
            if (!graph.count(city.num)) {
                continue;
            }
            for (auto it = graph[city.num].begin(); it != graph[city.num].end(); it++) {
                inDegree[(*it)]--;
                if (inDegree[(*it)] == 0) {
                    prty.push(citys[(*it)]);
                }
            }
        }
        return cnt;
    }
};