106172024-04-06 19:29:06AblablablaAutópálya inflációcpp17Wrong answer 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";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Wrong answer9ms2892 KiB
subtask20/8
3Accepted6ms2828 KiB
4Wrong answer6ms3068 KiB
5Wrong answer7ms3320 KiB
6Wrong answer7ms3628 KiB
7Wrong answer7ms3860 KiB
subtask30/15
8Wrong answer3ms3724 KiB
9Accepted3ms3792 KiB
10Accepted3ms3900 KiB
11Wrong answer3ms3868 KiB
12Wrong answer2ms3868 KiB
13Wrong answer2ms3876 KiB
14Wrong answer2ms3880 KiB
15Wrong answer3ms3912 KiB
16Accepted3ms3904 KiB
17Accepted3ms4032 KiB
18Wrong answer3ms4100 KiB
subtask40/34
19Accepted8ms4816 KiB
20Wrong answer8ms5036 KiB
21Wrong answer8ms4952 KiB
22Accepted8ms5032 KiB
23Accepted8ms5208 KiB
24Wrong answer8ms5268 KiB
25Accepted8ms5220 KiB
26Accepted8ms5312 KiB
27Wrong answer8ms5156 KiB
28Wrong answer6ms5048 KiB
29Wrong answer6ms5088 KiB
30Wrong answer6ms5112 KiB
31Wrong answer6ms5156 KiB
32Wrong answer8ms5664 KiB
33Wrong answer8ms5748 KiB
subtask50/21
34Wrong answer4ms5276 KiB
35Wrong answer4ms5572 KiB
36Wrong answer4ms5704 KiB
37Wrong answer4ms5732 KiB
38Wrong answer4ms5772 KiB
39Wrong answer4ms5924 KiB
40Wrong answer4ms5816 KiB
41Wrong answer4ms5996 KiB
42Wrong answer3ms6020 KiB
43Wrong answer3ms6032 KiB
44Wrong answer3ms6092 KiB
45Wrong answer3ms6364 KiB
46Wrong answer3ms6196 KiB
47Wrong answer3ms6204 KiB
48Wrong answer4ms6236 KiB
49Wrong answer4ms6304 KiB
subtask60/22
50Wrong answer9ms6988 KiB
51Wrong answer10ms7168 KiB
52Wrong answer10ms7280 KiB
53Wrong answer10ms7364 KiB
54Wrong answer10ms7512 KiB
55Wrong answer9ms7576 KiB
56Wrong answer8ms7464 KiB
57Wrong answer8ms7820 KiB
58Wrong answer4ms7420 KiB
59Wrong answer7ms7856 KiB
60Wrong answer7ms8004 KiB
61Wrong answer7ms8060 KiB
62Wrong answer7ms8228 KiB
63Wrong answer6ms8120 KiB
64Wrong answer10ms8532 KiB
65Wrong answer9ms8744 KiB
66Wrong answer9ms8828 KiB