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
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <queue>
using namespace std;
const long long INF = numeric_limits<long long>::max();

struct Jelly {
    int mass, price;
};

struct PQEntry {
    long long price;
    int r;

    bool operator<(const PQEntry& other) const {
        return price > other.price;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // input
    int n, k, m;
    cin >> n >> k >> m;
    vector<vector<Jelly>> J(k);
    for (int i=0; i<n; i++) {
        int color, mass, price;
        cin >> color >> mass >> price;
        J[color-1].push_back({mass, price});
    }

    // prepare packages
    vector<long long>BPFR(m, INF), buffer(m);
    BPFR[0] = 0;
    for (int c=0; c<k; c++) {
        fill(buffer.begin(), buffer.end(), INF);
        for (int r=0; r<m; r++)
            if (BPFR[r] != INF)
                for (const auto& j : J[c]) {
                    int rr = (r + j.mass) % m;
                    long long pp = BPFR[r] + j.price;
                    buffer[rr] = min(buffer[rr], pp);
                }
        BPFR.swap(buffer);
    }

    // Dijkstra
    vector<bool> Processed(m, false);
    vector<long long> BestPrice(m, INF);
    priority_queue<PQEntry> PQ;

    BestPrice[0] = 0;
    PQ.push({0, 0});

    while (!PQ.empty()) {
        int r = PQ.top().r;
        PQ.pop();
        if (Processed[r])
            continue;
        Processed[r] = true;

        for (int r2=0; r2<m; r2++)
            if (BPFR[r2] != INF) {
                int rr = (r + r2) % m;
                long long pp = BestPrice[r] + BPFR[r2];
                if (pp < BestPrice[rr]) {
                    BestPrice[rr] = pp;
                    PQ.push({pp, rr});
                }
            }
    }
    
    for (int r=0; r<m; r++)
        cout << (BestPrice[r]==INF ? -1 : BestPrice[r]) << '\n';
    return 0;
}