104762024-04-03 10:29:50Valaki2Autópálya inflációcpp17Runtime error 8/100185ms10700 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 3100;
const int mod = 1e9 + 7;

int n, m;
vector<pii > graph[1 + maxn];
int pow2[1 + maxn];
int dist[1 + maxn];

void dfs(int cur, int par, int depth) {
    for(pii nei : graph[cur]) {
        if(nei.fi != par) {
            dist[nei.fi] = (dist[cur] + nei.se * pow2[depth]) % mod;
            dfs(nei.fi, cur, depth + 1);
        }
    }
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].pb(mp(b, c));
        graph[b].pb(mp(a, c));
    }
    pow2[0] = 1;
    for(int i = 1; i <= n; i++) {
        pow2[i] = (2 * pow2[i - 1]) % mod;
    }
    dfs(1, -1, 0);
    for(int i = 2; i <= n; i++) {
        cout << dist[i] << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Runtime error4ms4304 KiB
2Runtime error7ms5396 KiB
subtask28/8
3Accepted4ms3084 KiB
4Accepted4ms3332 KiB
5Accepted4ms3580 KiB
6Accepted4ms3764 KiB
7Accepted4ms4456 KiB
subtask30/15
8Accepted3ms3820 KiB
9Runtime error3ms6108 KiB
10Runtime error4ms6244 KiB
11Runtime error4ms6388 KiB
12Runtime error4ms6352 KiB
13Runtime error4ms6344 KiB
14Runtime error4ms6360 KiB
15Runtime error4ms6492 KiB
16Runtime error4ms6568 KiB
17Runtime error4ms6576 KiB
18Runtime error4ms6696 KiB
subtask40/34
19Runtime error6ms7460 KiB
20Runtime error8ms7536 KiB
21Runtime error8ms7600 KiB
22Runtime error6ms7680 KiB
23Runtime error6ms7636 KiB
24Runtime error9ms7984 KiB
25Runtime error6ms8096 KiB
26Runtime error6ms8124 KiB
27Runtime error6ms7960 KiB
28Runtime error4ms7968 KiB
29Runtime error4ms8004 KiB
30Runtime error4ms7824 KiB
31Runtime error4ms8004 KiB
32Runtime error6ms8268 KiB
33Runtime error6ms8332 KiB
subtask50/21
34Runtime error185ms7756 KiB
35Runtime error4ms7956 KiB
36Runtime error4ms8116 KiB
37Runtime error4ms8244 KiB
38Runtime error4ms8268 KiB
39Runtime error4ms8308 KiB
40Runtime error4ms8336 KiB
41Runtime error4ms8364 KiB
42Runtime error4ms8308 KiB
43Runtime error4ms8212 KiB
44Runtime error4ms8376 KiB
45Runtime error4ms8236 KiB
46Runtime error4ms8252 KiB
47Runtime error4ms8256 KiB
48Runtime error4ms8352 KiB
49Runtime error4ms8456 KiB
subtask60/22
50Runtime error35ms9160 KiB
51Runtime error7ms9148 KiB
52Runtime error6ms9264 KiB
53Runtime error7ms9516 KiB
54Runtime error6ms9488 KiB
55Runtime error6ms9748 KiB
56Runtime error6ms9484 KiB
57Runtime error6ms9576 KiB
58Runtime error4ms9204 KiB
59Runtime error6ms9744 KiB
60Runtime error4ms10048 KiB
61Runtime error4ms9952 KiB
62Runtime error4ms10084 KiB
63Runtime error4ms10144 KiB
64Runtime error7ms10596 KiB
65Runtime error6ms10700 KiB
66Runtime error6ms10652 KiB