10477 2024. 04. 03 10:48:49 Valaki2 Autópálya infláció cpp17 Futási hiba 15/100 4ms 5248 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();
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Futási hiba 3ms 2068 KiB
subtask2 0/8
3 Futási hiba 3ms 2312 KiB
4 Futási hiba 3ms 2548 KiB
5 Futási hiba 3ms 2744 KiB
6 Futási hiba 3ms 2992 KiB
7 Futási hiba 3ms 3052 KiB
subtask3 15/15
8 Elfogadva 3ms 3292 KiB
9 Elfogadva 3ms 3412 KiB
10 Elfogadva 2ms 3380 KiB
11 Elfogadva 2ms 3264 KiB
12 Elfogadva 3ms 3396 KiB
13 Elfogadva 3ms 3616 KiB
14 Elfogadva 3ms 3648 KiB
15 Elfogadva 3ms 3788 KiB
16 Elfogadva 2ms 3756 KiB
17 Elfogadva 2ms 3648 KiB
18 Elfogadva 2ms 3644 KiB
subtask4 0/34
19 Futási hiba 3ms 3756 KiB
20 Futási hiba 3ms 3884 KiB
21 Futási hiba 3ms 3916 KiB
22 Futási hiba 3ms 4028 KiB
23 Futási hiba 3ms 4096 KiB
24 Futási hiba 3ms 4096 KiB
25 Futási hiba 3ms 4152 KiB
26 Futási hiba 3ms 4160 KiB
27 Futási hiba 3ms 4160 KiB
28 Futási hiba 3ms 4160 KiB
29 Futási hiba 3ms 4180 KiB
30 Futási hiba 3ms 4260 KiB
31 Futási hiba 3ms 4156 KiB
32 Futási hiba 3ms 4156 KiB
33 Futási hiba 3ms 4152 KiB
subtask5 0/21
34 Futási hiba 3ms 4284 KiB
35 Futási hiba 3ms 4284 KiB
36 Futási hiba 3ms 4188 KiB
37 Futási hiba 3ms 4160 KiB
38 Futási hiba 3ms 4184 KiB
39 Futási hiba 3ms 4176 KiB
40 Futási hiba 3ms 4176 KiB
41 Futási hiba 3ms 4176 KiB
42 Futási hiba 4ms 4548 KiB
43 Futási hiba 3ms 4240 KiB
44 Futási hiba 3ms 4348 KiB
45 Futási hiba 3ms 4352 KiB
46 Futási hiba 3ms 4468 KiB
47 Futási hiba 3ms 4468 KiB
48 Futási hiba 4ms 4928 KiB
49 Futási hiba 3ms 4444 KiB
subtask6 0/22
50 Futási hiba 3ms 4572 KiB
51 Futási hiba 3ms 4576 KiB
52 Futási hiba 3ms 4580 KiB
53 Futási hiba 3ms 4448 KiB
54 Futási hiba 3ms 4448 KiB
55 Futási hiba 3ms 4576 KiB
56 Futási hiba 3ms 4812 KiB
57 Futási hiba 3ms 5016 KiB
58 Futási hiba 3ms 5116 KiB
59 Futási hiba 3ms 5224 KiB
60 Futási hiba 3ms 5248 KiB
61 Futási hiba 3ms 5120 KiB
62 Futási hiba 3ms 5116 KiB
63 Futási hiba 3ms 5232 KiB
64 Futási hiba 3ms 5232 KiB
65 Futási hiba 3ms 5128 KiB
66 Futási hiba 3ms 5084 KiB