제출 #1213596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213596		Ghulam_Junaid	Paths (RMI21_paths)	C++20	0 / 100	0 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 2005;
int n, k, par[N], mark[N], d[N];
vector<pair<int, int>> g[N];

void dfs(int v, int p = 0){
    for (auto [w, u] : g[v]){
        if (u == p) continue;
        par[u] = v;
        d[u] = d[v] + w * (!mark[u]);
        dfs(u, v);
    }
}

int main(){
    cin >> n >> k;
    for (int i = 0; i < n - 1; i ++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({w, v});
        g[v].push_back({w, u});
    }

    for (int v = 1; v <= n; v ++){
        memset(mark, 0, sizeof mark);
        d[v] = 0;
        int ans = 0;
        for (int i = 0; i < k; i ++){
            dfs(v);
            
            int u = 1;
            for (int j = 1; j <= n; j ++)
                if (d[u] < d[j])
                    u = j;
            ans += d[u];

            while (1){
                mark[u] = 1;
                if (u == v) break;
                u = par[u];
            }
        }

        cout << ans << '\n';
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32