题解 | #旅行Ⅰ#

拓扑排序

拓扑排序的核心在于维护每个节点的入度，每个节点会指向其他的节点，记录释放当前节点能减少入度的节点列表，同时维护一个优先队列，用结构体自定义排序算法。需要注意的是下标有时从1开始，有时从0开始，我的想法是做题前统一转化成从0开始，避免混乱。

 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    struct cmp {
        bool operator() (pair<int, int>& p1, pair<int, int>& p2) {
            if (p1.first == p2.first) {
                return p1.second > p2.second;
            } else {
                return p1.first > p2.first;
            }
        }
    };
    int Travel(int N, int V, vector<int>& A, vector<Point>& list) {
        // write code here
        // 使用拓扑排序维护能去的城市
        vector<int> indegree(N, 0);
        unordered_map<int, vector<int>> point_to;  // 指向的点矩阵，key释放后这些点的入度减1
        for (Point& p : list) {
            ++indegree[p.y - 1];   // 用下标0表示1号
            point_to[p.x - 1].push_back(p.y - 1);
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> myQue;
        for (int i = 0; i < N; ++i) {
            if (indegree[i] == 0) {
                myQue.push({A[i], i});
            }
        }
        int ans = 0;
        int cost_sum = 0;
        while (!myQue.empty()) {
            pair<int, int> cost_num = myQue.top();
            myQue.pop();
            cost_sum += cost_num.first;
            cout << cost_sum << endl;
            if (V < cost_sum) {
                break;
            }
            ++ans;
            for (int& p : point_to[cost_num.second]) {
                --indegree[p];
                if (indegree[p] == 0) {
                    myQue.push({A[p], p});
                }
            }
        }
        return ans;
    }
};