10617 2024. 04. 06 19:29:06 Ablablabla Autópálya infláció cpp17 Hibás válasz 0/100 10ms 8828 KiB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int INF = 2e9 + 7;
const int MOD = 1e9 + 7;

int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<pii>> csucsok(n, vector<pii>());
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        csucsok[a].push_back({b, c});
        csucsok[b].push_back({a, c});
    }

    vector<int> szorzo(n + 1);
    szorzo[0] = 1;
    for(int i = 1; i <= n; i++){
        szorzo[i] = 2 * szorzo[i - 1];
        szorzo[i] %= MOD;
    }

    queue<int> bejar;
    vector<int> tavok(n, INF);
    bejar.push(0);
    tavok[0] = 0;
    vector<int> melyseg(n, 0);

    while(!bejar.empty()){
        int akt = bejar.front();
        bejar.pop();

        for(pii x : csucsok[akt]){
            int ert = tavok[akt] + x.second * szorzo[melyseg[akt]];
            ert %= MOD;

            if(tavok[x.first] > ert){
                tavok[x.first] = ert;
                melyseg[x.first] = melyseg[akt] + 1;
                bejar.push(x.first);
            }
        }
    }

    for(int i = 1; i < n; i++){
        cout << tavok[i] << "\n";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1812 KiB
2 Hibás válasz 9ms 2892 KiB
subtask2 0/8
3 Elfogadva 6ms 2828 KiB
4 Hibás válasz 6ms 3068 KiB
5 Hibás válasz 7ms 3320 KiB
6 Hibás válasz 7ms 3628 KiB
7 Hibás válasz 7ms 3860 KiB
subtask3 0/15
8 Hibás válasz 3ms 3724 KiB
9 Elfogadva 3ms 3792 KiB
10 Elfogadva 3ms 3900 KiB
11 Hibás válasz 3ms 3868 KiB
12 Hibás válasz 2ms 3868 KiB
13 Hibás válasz 2ms 3876 KiB
14 Hibás válasz 2ms 3880 KiB
15 Hibás válasz 3ms 3912 KiB
16 Elfogadva 3ms 3904 KiB
17 Elfogadva 3ms 4032 KiB
18 Hibás válasz 3ms 4100 KiB
subtask4 0/34
19 Elfogadva 8ms 4816 KiB
20 Hibás válasz 8ms 5036 KiB
21 Hibás válasz 8ms 4952 KiB
22 Elfogadva 8ms 5032 KiB
23 Elfogadva 8ms 5208 KiB
24 Hibás válasz 8ms 5268 KiB
25 Elfogadva 8ms 5220 KiB
26 Elfogadva 8ms 5312 KiB
27 Hibás válasz 8ms 5156 KiB
28 Hibás válasz 6ms 5048 KiB
29 Hibás válasz 6ms 5088 KiB
30 Hibás válasz 6ms 5112 KiB
31 Hibás válasz 6ms 5156 KiB
32 Hibás válasz 8ms 5664 KiB
33 Hibás válasz 8ms 5748 KiB
subtask5 0/21
34 Hibás válasz 4ms 5276 KiB
35 Hibás válasz 4ms 5572 KiB
36 Hibás válasz 4ms 5704 KiB
37 Hibás válasz 4ms 5732 KiB
38 Hibás válasz 4ms 5772 KiB
39 Hibás válasz 4ms 5924 KiB
40 Hibás válasz 4ms 5816 KiB
41 Hibás válasz 4ms 5996 KiB
42 Hibás válasz 3ms 6020 KiB
43 Hibás válasz 3ms 6032 KiB
44 Hibás válasz 3ms 6092 KiB
45 Hibás válasz 3ms 6364 KiB
46 Hibás válasz 3ms 6196 KiB
47 Hibás válasz 3ms 6204 KiB
48 Hibás válasz 4ms 6236 KiB
49 Hibás válasz 4ms 6304 KiB
subtask6 0/22
50 Hibás válasz 9ms 6988 KiB
51 Hibás válasz 10ms 7168 KiB
52 Hibás válasz 10ms 7280 KiB
53 Hibás válasz 10ms 7364 KiB
54 Hibás válasz 10ms 7512 KiB
55 Hibás válasz 9ms 7576 KiB
56 Hibás válasz 8ms 7464 KiB
57 Hibás válasz 8ms 7820 KiB
58 Hibás válasz 4ms 7420 KiB
59 Hibás válasz 7ms 7856 KiB
60 Hibás válasz 7ms 8004 KiB
61 Hibás válasz 7ms 8060 KiB
62 Hibás válasz 7ms 8228 KiB
63 Hibás válasz 6ms 8120 KiB
64 Hibás válasz 10ms 8532 KiB
65 Hibás válasz 9ms 8744 KiB
66 Hibás válasz 9ms 8828 KiB