悬赏
  • 板块灌水区
  • 楼主Fu_xuan_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/7 18:54
  • 上次更新2024/8/7 20:10:20
查看原帖
悬赏
1288007
Fu_xuan_楼主2024/8/7 18:54

求助,RE了,帮忙,悬赏1关 题目传送门

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 10100;
const int INF = 1e9+10;

class Solution {
public:
    vector<int> ans;
    vector<pair<int, int>> g[MAXN];
    int dist[MAXN];
    int t;

    void dfs(int i, int fa) {
        for (auto& e : g[i]) {
            int j = e.first, w = e.second;
            if (j != fa) {
                dist[j] = min(dist[j], dist[i] + w);
                dfs(j, i);
            }
        }
        ans[i] = dist[i] <= t;
    }

    void solve(int n, int t) {
        this->t = t;
        fill(dist, dist + MAXN, INF);
        for (int i = 0; i < n; ++i) {
            ans[i] = 1;
        }
        dist[0] = 0;
        for (int i = 1; i < n; ++i) {
            int p, w;
            cin >> p >> w;
            g[p].push_back({i, w});
            g[i].push_back({p, w});
        }
        dfs(0, -1);
        for (int i = 1; i <= n; ++i) {
            cout << ans[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Solution s;
    int n, t;
    cin >> n >> t;
    s.solve(n, t);
    return 0;
}
2024/8/7 18:54
加载中...