104772024-04-03 10:48:49Valaki2Autópálya inflációcpp17Futási hiba 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();
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Futási hiba3ms2068 KiB
subtask20/8
3Futási hiba3ms2312 KiB
4Futási hiba3ms2548 KiB
5Futási hiba3ms2744 KiB
6Futási hiba3ms2992 KiB
7Futási hiba3ms3052 KiB
subtask315/15
8Elfogadva3ms3292 KiB
9Elfogadva3ms3412 KiB
10Elfogadva2ms3380 KiB
11Elfogadva2ms3264 KiB
12Elfogadva3ms3396 KiB
13Elfogadva3ms3616 KiB
14Elfogadva3ms3648 KiB
15Elfogadva3ms3788 KiB
16Elfogadva2ms3756 KiB
17Elfogadva2ms3648 KiB
18Elfogadva2ms3644 KiB
subtask40/34
19Futási hiba3ms3756 KiB
20Futási hiba3ms3884 KiB
21Futási hiba3ms3916 KiB
22Futási hiba3ms4028 KiB
23Futási hiba3ms4096 KiB
24Futási hiba3ms4096 KiB
25Futási hiba3ms4152 KiB
26Futási hiba3ms4160 KiB
27Futási hiba3ms4160 KiB
28Futási hiba3ms4160 KiB
29Futási hiba3ms4180 KiB
30Futási hiba3ms4260 KiB
31Futási hiba3ms4156 KiB
32Futási hiba3ms4156 KiB
33Futási hiba3ms4152 KiB
subtask50/21
34Futási hiba3ms4284 KiB
35Futási hiba3ms4284 KiB
36Futási hiba3ms4188 KiB
37Futási hiba3ms4160 KiB
38Futási hiba3ms4184 KiB
39Futási hiba3ms4176 KiB
40Futási hiba3ms4176 KiB
41Futási hiba3ms4176 KiB
42Futási hiba4ms4548 KiB
43Futási hiba3ms4240 KiB
44Futási hiba3ms4348 KiB
45Futási hiba3ms4352 KiB
46Futási hiba3ms4468 KiB
47Futási hiba3ms4468 KiB
48Futási hiba4ms4928 KiB
49Futási hiba3ms4444 KiB
subtask60/22
50Futási hiba3ms4572 KiB
51Futási hiba3ms4576 KiB
52Futási hiba3ms4580 KiB
53Futási hiba3ms4448 KiB
54Futási hiba3ms4448 KiB
55Futási hiba3ms4576 KiB
56Futási hiba3ms4812 KiB
57Futási hiba3ms5016 KiB
58Futási hiba3ms5116 KiB
59Futási hiba3ms5224 KiB
60Futási hiba3ms5248 KiB
61Futási hiba3ms5120 KiB
62Futási hiba3ms5116 KiB
63Futási hiba3ms5232 KiB
64Futási hiba3ms5232 KiB
65Futási hiba3ms5128 KiB
66Futási hiba3ms5084 KiB