104772024-04-03 10:48:49Valaki2Autópálya inflációcpp17Runtime error 15/1004ms5248 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 = 10;
const int mod = 1e9 + 7;
const int inf = 1e18 + 7;

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

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));
    }
    priority_queue<pair<int, pii > > q;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            dist[i][j] = inf;
        }
    }
    dist[1][0] = 0;
    q.push(mp(0, mp(1, 0)));
    while(!q.empty()) {
        pii curpair = q.top().se;
        q.pop();
        int cur = curpair.fi, cur_steps = curpair.se;
        if(done[cur][cur_steps]) {
            continue;
        }
        done[cur][cur_steps] = true;
        if(cur_steps >= n) {
            continue;
        }
        for(pii nei : graph[cur]) {
            int neidist = dist[cur][cur_steps] + (1 << cur_steps) * nei.se;
            if(neidist < dist[nei.fi][cur_steps + 1]) {
                dist[nei.fi][cur_steps + 1] = neidist;
                q.push(mp(-neidist, mp(nei.fi, cur_steps + 1)));
            }
        }
    }
    for(int i = 2; i <= n; i++) {
        int ans = inf;
        for(int j = 0; j <= n; j++) {
            ans = min(ans, dist[i][j]);
        }
        cout << ans % mod << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Runtime error3ms2068 KiB
subtask20/8
3Runtime error3ms2312 KiB
4Runtime error3ms2548 KiB
5Runtime error3ms2744 KiB
6Runtime error3ms2992 KiB
7Runtime error3ms3052 KiB
subtask315/15
8Accepted3ms3292 KiB
9Accepted3ms3412 KiB
10Accepted2ms3380 KiB
11Accepted2ms3264 KiB
12Accepted3ms3396 KiB
13Accepted3ms3616 KiB
14Accepted3ms3648 KiB
15Accepted3ms3788 KiB
16Accepted2ms3756 KiB
17Accepted2ms3648 KiB
18Accepted2ms3644 KiB
subtask40/34
19Runtime error3ms3756 KiB
20Runtime error3ms3884 KiB
21Runtime error3ms3916 KiB
22Runtime error3ms4028 KiB
23Runtime error3ms4096 KiB
24Runtime error3ms4096 KiB
25Runtime error3ms4152 KiB
26Runtime error3ms4160 KiB
27Runtime error3ms4160 KiB
28Runtime error3ms4160 KiB
29Runtime error3ms4180 KiB
30Runtime error3ms4260 KiB
31Runtime error3ms4156 KiB
32Runtime error3ms4156 KiB
33Runtime error3ms4152 KiB
subtask50/21
34Runtime error3ms4284 KiB
35Runtime error3ms4284 KiB
36Runtime error3ms4188 KiB
37Runtime error3ms4160 KiB
38Runtime error3ms4184 KiB
39Runtime error3ms4176 KiB
40Runtime error3ms4176 KiB
41Runtime error3ms4176 KiB
42Runtime error4ms4548 KiB
43Runtime error3ms4240 KiB
44Runtime error3ms4348 KiB
45Runtime error3ms4352 KiB
46Runtime error3ms4468 KiB
47Runtime error3ms4468 KiB
48Runtime error4ms4928 KiB
49Runtime error3ms4444 KiB
subtask60/22
50Runtime error3ms4572 KiB
51Runtime error3ms4576 KiB
52Runtime error3ms4580 KiB
53Runtime error3ms4448 KiB
54Runtime error3ms4448 KiB
55Runtime error3ms4576 KiB
56Runtime error3ms4812 KiB
57Runtime error3ms5016 KiB
58Runtime error3ms5116 KiB
59Runtime error3ms5224 KiB
60Runtime error3ms5248 KiB
61Runtime error3ms5120 KiB
62Runtime error3ms5116 KiB
63Runtime error3ms5232 KiB
64Runtime error3ms5232 KiB
65Runtime error3ms5128 KiB
66Runtime error3ms5084 KiB