题解 | #旅行Ⅰ#

思路：

题目的主要信息：

• 一个N个城市，A数组中记录的是访问每个城市所需的花费，V是初始所有的总预算
• 如果同时访问了两个城市，需要满足List中Point记录的先后顺序
• 优先访问花费最小的城市，第二优先级是下标最小
• 求满足预算条件下，最多访问的城市数

因为有优先级，我们用到了一个优先队列，并且重载了比较符号。

方法一：暴力解法
具体做法：
直接模拟访问过程，city数组保存城市之间的次序关系，dp数组保存每个城市的前序访问还剩下多少个，flag记录该城市有无被访问过，初始时没有前序城市的城市先入队列。我们可以遍历队列，每次弹出都是花费最小或者下标最小的城市，我们访问该城市，然后将其相邻的后续城市的前序数量减一，最后我们遍历每个城市，如果该城市的前序为0且没有被访问过，则加入优先队列中，等待访问。
这其中使用到了拓扑排序的思想。

class Solution {
public:
     struct node{
        int val;
        int index;
        bool friend operator <(node a, node b) { //花费优先，然后时下标
            if(a.val == b.val) 
                return a.index > b.index;  
            return a.val > b.val;
        }
    };
    int Travel(int N, int V, vector<int>& A, vector<Point>& list) {
        vector<int> dp(N + 1, 0); //记录有多少个前序城市
        int res = 0;
        vector<vector<int> > city(N + 1, vector<int> ()); //记录城市之间的次序
        for(int i = 0; i < list.size(); i++){
            city[list[i].x].push_back(list[i].y);
            dp[list[i].y]++; 
        }
        priority_queue<node> q;
        vector<bool> flag(N + 1, false);
        for(int i = 1; i <= N; i++){
            if(dp[i] == 0){
                q.push({A[i - 1], i});  //没有前序的城市可以直接放入队列，优先访问花费最小的
                flag[i] = true; //记录访问过该点
            }
        }
        while(!q.empty()){
            node temp = q.top();
            q.pop();
            if(temp.val > V)  //预算不够了
                break;
            V -= temp.val;
            res++;
            for(int i = 0; i < city[temp.index].size(); i++) //该城市的所有后序城市的前序数量减一
                dp[city[temp.index][i]]--;
            for(int i = 1; i <= N; i++){ //遍历每个城市，如果该城市的前序为0且没有被访问过
                if(dp[i] == 0 && !flag[i]){
                    q.push({A[i - 1], i});
                    flag[i] = true;
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，优先队列每次存入是，最坏嵌套遍历两次数组
• 空间复杂度：，优先队列、辅助数组dp、flag都是，但是记录城市次序的数组最坏可能达到

方法二：优化
具体做法：
方法一，我们使用了flag数组记录城市有无被访问过，这其实是旅行Ⅱ 的遗留问题，在这题中一旦我们使用了优先队列，那么每次dp数组中的元素归零时，它一定还没有被访问过，而只可能收到这个前序城市的影响，因此我们可以将其直接加入队列中，不需要使用flag数组。如图所示，图中以小顶堆代替优先队列：

从后面的分析中，我们可以看到虽然最坏的时间复杂度没有变化，但是整体性能有多提高，平局时间和空间都有减少。

class Solution {
public:
     struct node{
        int val;
        int index;
        bool friend operator <(node a, node b) {//花费优先，然后时下标
            if(a.val == b.val) 
                return a.index > b.index;
            return a.val > b.val;
        }
    };
    int Travel(int N, int V, vector<int>& A, vector<Point>& list) {
        vector<int> dp(N + 1, 0); //记录有多少个前序城市
        int res = 0;
        vector<vector<int> > city(N + 1, vector<int> ()); //记录城市之间的次序
        for(int i = 0; i < list.size(); i++){
            city[list[i].x].push_back(list[i].y);
            dp[list[i].y]++;
        }
        priority_queue<node> q;
        for(int i = 1; i <= N; i++)
            if(dp[i] == 0)
                q.push({A[i - 1], i});
        while(!q.empty()){
            node temp = q.top();
            q.pop();
            if(temp.val > V)  //预算不够了
                break;
            V -= temp.val;
            res++;
            for(int i = 0; i < city[temp.index].size(); i++){ //该城市的所有后序城市的前序数量减一
                dp[city[temp.index][i]]--;  
                if(dp[city[temp.index][i]] == 0)  //刚刚为0的城市一定还没有被访问过
                    q.push({A[city[temp.index][i] - 1], city[temp.index][i]});
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，优先队列每次存入是，最坏情况是一个城市之间的次序是一个无向完全图，city数组第二维平均大小为
• 空间复杂度：，为最坏时city数组的大小