106172024-04-06 19:29:06AblablablaAutópálya inflációcpp17Hibás válasz 0/10010ms8828 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Hibás válasz9ms2892 KiB
subtask20/8
3Elfogadva6ms2828 KiB
4Hibás válasz6ms3068 KiB
5Hibás válasz7ms3320 KiB
6Hibás válasz7ms3628 KiB
7Hibás válasz7ms3860 KiB
subtask30/15
8Hibás válasz3ms3724 KiB
9Elfogadva3ms3792 KiB
10Elfogadva3ms3900 KiB
11Hibás válasz3ms3868 KiB
12Hibás válasz2ms3868 KiB
13Hibás válasz2ms3876 KiB
14Hibás válasz2ms3880 KiB
15Hibás válasz3ms3912 KiB
16Elfogadva3ms3904 KiB
17Elfogadva3ms4032 KiB
18Hibás válasz3ms4100 KiB
subtask40/34
19Elfogadva8ms4816 KiB
20Hibás válasz8ms5036 KiB
21Hibás válasz8ms4952 KiB
22Elfogadva8ms5032 KiB
23Elfogadva8ms5208 KiB
24Hibás válasz8ms5268 KiB
25Elfogadva8ms5220 KiB
26Elfogadva8ms5312 KiB
27Hibás válasz8ms5156 KiB
28Hibás válasz6ms5048 KiB
29Hibás válasz6ms5088 KiB
30Hibás válasz6ms5112 KiB
31Hibás válasz6ms5156 KiB
32Hibás válasz8ms5664 KiB
33Hibás válasz8ms5748 KiB
subtask50/21
34Hibás válasz4ms5276 KiB
35Hibás válasz4ms5572 KiB
36Hibás válasz4ms5704 KiB
37Hibás válasz4ms5732 KiB
38Hibás válasz4ms5772 KiB
39Hibás válasz4ms5924 KiB
40Hibás válasz4ms5816 KiB
41Hibás válasz4ms5996 KiB
42Hibás válasz3ms6020 KiB
43Hibás válasz3ms6032 KiB
44Hibás válasz3ms6092 KiB
45Hibás válasz3ms6364 KiB
46Hibás válasz3ms6196 KiB
47Hibás válasz3ms6204 KiB
48Hibás válasz4ms6236 KiB
49Hibás válasz4ms6304 KiB
subtask60/22
50Hibás válasz9ms6988 KiB
51Hibás válasz10ms7168 KiB
52Hibás válasz10ms7280 KiB
53Hibás válasz10ms7364 KiB
54Hibás válasz10ms7512 KiB
55Hibás válasz9ms7576 KiB
56Hibás válasz8ms7464 KiB
57Hibás válasz8ms7820 KiB
58Hibás válasz4ms7420 KiB
59Hibás válasz7ms7856 KiB
60Hibás válasz7ms8004 KiB
61Hibás válasz7ms8060 KiB
62Hibás válasz7ms8228 KiB
63Hibás válasz6ms8120 KiB
64Hibás válasz10ms8532 KiB
65Hibás válasz9ms8744 KiB
66Hibás válasz9ms8828 KiB