题解 | #旅行Ⅰ#

算法思想一：暴力法

解题思路：

对于求解本题牛妹最多能到多少个城市去旅游，我们可以直接模拟牛妹的访问过程，首先我们定义city，dp，flag数组，分别记录城市之间的次序关系，每个城市的前序访问和该城市有无被访问过。然后我们开始进行模拟访问，首先没有前序城市的城市进入队列，每次花费最小或者下标最小的城市出队，然后将相邻的后续城市的前序数量减一。最后我们可以遍历完所有城市，并且根据花费，计算出牛妹最多可以到达多少个城市去旅游。

整个过程使用了拓扑排序的思想

图解：

代码展示：

C++版本

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型vector A
     * @param list Point类vector List
     * @return int整型
     */
    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) {
        // write code here
        vector dp(N + 1, 0); // 记录有多少个前序城市
        int res = 0; // 声明结果
        vector > city(N + 1, vector ()); // 记录城市之间的次序
        for(int i = 0; i < list.size(); i++)
        {
            city[list[i].x].push_back(list[i].y); // 城市入队
            dp[list[i].y]++;
        }
        priority_queue q;
        vector flag(N + 1, false); // 声明flag数组来记录该城市是否被访问
        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; // 返回结果
    }
};

复杂度分析

时间复杂度 $O(N^2logN)$ ：两层循环加一个队列时间 $O(N^2logN)$

空间复杂度 $O(N^2)$ ：使用额外数组，因此空间复杂度为 $O(N^2)$

算法思想二：方法一优化