1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;

struct zelek{
    int masa;
    ll cena;
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k, m;
    cin >> n >> k >> m;
    vector<vector<zelek>> kolory (k+1);
    for (int i = 0; i < n; i++){
        int kolor, masa;
        ll cena;
        cin >> kolor >> masa >> cena;
        kolory[kolor].push_back({masa, cena});
    }

    vector<ll> min_cena1 (m, 1'000'000'000'000'000'000);
    vector<ll> min_cena2 (m, 1'000'000'000'000'000'000);

    for (int i = 0; i < kolory[1].size(); i++){
        min_cena1[kolory[1][i].masa%m] = min(min_cena1[kolory[1][i].masa%m], kolory[1][i].cena);
    }

    for (int i = 2; i <= k; i++){
        for (int j = 0; j < kolory[i].size(); j++){
            for (int l = 0; l < m; l++){
                if (min_cena1[l] != 1'000'000'000'000'000'000){
                    min_cena2[(l+kolory[i][j].masa)%m] = min(min_cena2[(l+kolory[i][j].masa)%m], min_cena1[l] + kolory[i][j].cena);
                }
            }
        }
        min_cena1 = min_cena2;
        min_cena2 = vector<ll> (m, 1'000'000'000'000'000'000);
    }

    /*for (int i = 0; i < m; i++){
        cout << min_cena1[i] << " ";
    }
    cout << endl;*/

    vector<pair<int, ll>> osiagniete;
    for (int i = 0; i < m; i++){
        if (min_cena1[i] != 1'000'000'000'000'000'000){
            osiagniete.push_back({i, min_cena1[i]});
        }
    }

    //dijkstra
    vector<vector<pair<int, ll>>> sasiedzi (m);
    for (int i = 0; i < m; i++){
        for (int j = 0; j < osiagniete.size(); j++){
            sasiedzi[i].push_back({(i+osiagniete[j].first)%m, osiagniete[j].second});
        }
    }

    vector<ll> odleglosc (m, 1'000'000'000'000'000'000);
    odleglosc[0] = 0;
    vector<bool> odwiedzone (m, false);

    for (int i = 0; i < m; i++){
        ll najmniejsza = 1'000'000'000'000'000'001;
        int najmniejszy_indeks = -1;
        for (int j = 0; j < m; j++){
            if (!odwiedzone[j] && odleglosc[j] < najmniejsza){
                najmniejsza = odleglosc[j];
                najmniejszy_indeks = j;
            }
        }
        odwiedzone[najmniejszy_indeks] = true;
        for (int j = 0; j < sasiedzi[najmniejszy_indeks].size(); j++){
            if (odleglosc[sasiedzi[najmniejszy_indeks][j].first] > odleglosc[najmniejszy_indeks] + sasiedzi[najmniejszy_indeks][j].second){
                odleglosc[sasiedzi[najmniejszy_indeks][j].first] = odleglosc[najmniejszy_indeks] + sasiedzi[najmniejszy_indeks][j].second;
            }
        }
    }

    for (int i = 0; i < m; i++){
        if (odleglosc[i] != 1'000'000'000'000'000'000){
            cout << odleglosc[i] << "\n";
        }else{
            cout << -1 << "\n";
        }
    }
}