旅行Ⅰ题解

做法1：AC
按照题意模拟即可，因为要每次选择可达中花费最小的且编号最小的，所以我们用一个优先队列维护拓扑就好，从优先队列中取出花费&编号最小的，然后把这座城市所影响的城市的度数--，我们会发现变为0的只可能是这次度数--的城市，那么只需要将在这次操作中城市度数变为0的城市加入优先队列，然后重复上述操作直到钱不够或者走完了所有城市。时间复杂度为，空间复杂度为

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */
typedef long long ll;
class Solution {
public:
    /**
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型一维数组 A
     * @param ALen int A数组长度
     * @param List Point类vector List
     * @return int整型
     */
    struct node {
        ll val,id;
        bool friend operator <(node a,node b) {
            if(a.val==b.val) return a.id>b.id;
            return a.val>b.val;
        }
    }p;
    priority_queue<node>q;
    int Travel(int N, int V, int* A, int ALen, vector<Point>& List) {
        // write code here
        int du[N+1];
        vector<int>v[N+1];
        memset(du,0,sizeof du);
        for(auto i:List) {
            v[i.x].push_back(i.y);
            du[i.y]++;
        }
        for(int i=1;i<=N;i++) if(du[i]==0) q.push({A[i-1],i});
        int ans=0;
        while(!q.empty()) {
            p=q.top();
            q.pop();
            if(p.val>V) break;
            V-=p.val;
            ans++;
            for(auto i:v[p.id]) {
                du[i]--;
                if(du[i]==0)  q.push({A[i-1],i});
            }
        }
        return ans;
    }
};

做法2：TLE
按照题意模拟即可，因为要每次选择可达中花费最小的且编号最小的，所以我们用一个优先队列维护拓扑就好，从优先队列中取出花费&编号最小的，然后把这座城市影响的城市的度数--，然后的去寻找城市度数为0则加入优先队列，然后重复上述操作知道钱不够或者走完了所有城市。时间复杂度为，空间复杂度为

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */
typedef long long ll;
class Solution {
public:
    /**
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型一维数组 A
     * @param ALen int A数组长度
     * @param List Point类vector List
     * @return int整型
     */
    struct node {
        ll val,id;
        bool friend operator <(node a,node b) {
            if(a.val==b.val) return a.id>b.id;
            return a.val>b.val;
        }
    }p;
    priority_queue<node>q;
    int vis[100010];
    int Travel(int N, int V, int* A, int ALen, vector<Point>& List) {
        // write code here
        int du[N+1];
        vector<int>v[N+1];
        memset(du,0,sizeof du);
        for(auto i:List) {
            v[i.x].push_back(i.y);
            du[i.y]++;
        }
        for(int i=1;i<=N;i++) if(du[i]==0) q.push({A[i-1],i}),vis[i]=1;
        int ans=0;
        while(!q.empty()) {
            p=q.top();
            q.pop();
            if(p.val>V) break;
            V-=p.val;
            ans++;
            for(auto i:v[p.id]) 
                du[i]--;
            for(int i=1;i<=N;i++) if(du[i]==0&&!vis[i])  q.push({A[i-1],i}),vis[i]=1;
        }
        return ans;
    }
};