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
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>

typedef long long int LONG;
typedef std::pair<LONG, int> ELEMENT;

int main() {
    int N, K, M;
    std::vector<std::vector<std::pair<int, int> > > color_types;

    scanf("%d %d %d", &N, &K, &M);
    color_types.resize(K+1);

    for (int i=0; i<N; ++i) {
        int tk, tm, tc;
        scanf("%d %d %d", &tk, &tm, &tc);
        color_types[tk].emplace_back(tm, tc);
    }

    //possibilities when each color used single time
    std::vector<LONG> once(M, -1); // once[m] = min_price
    std::vector<LONG> once_new(M, -1);

    once[0] = 0;
    for (int color=1; color<=K; ++color) {
        for (const auto &pair : color_types[color]) {
            for (int i=0; i<M; ++i) {
                if (once[i] >= 0) {
                    int nm = (i+pair.first) % M;
                    if (once_new[nm] < 0) {
                        once_new[nm] = once[i] + pair.second;
                    } else {
                        once_new[nm] = std::min(once_new[nm], once[i] + pair.second);
                    }
                }
            }
        }
        once = once_new;
        once_new = std::vector<LONG>(M, -1);
    }

    std::vector<std::pair<LONG, int> > cand;
    for (int i=0; i<M; ++i) {
        if (once[i]>=0) {
            cand.emplace_back(once[i], i);
        }
    }

    std::priority_queue<ELEMENT, std::vector<ELEMENT>, std::greater<ELEMENT> > queue;
    std::vector<LONG> result(M, -1);
    queue.emplace(0, 0);
    result[0] = 0;

    while (!queue.empty()) {
        auto element = queue.top();
        queue.pop();

        if (result[element.second] != element.first) {
            continue;
        }

        for (auto& v : cand) {
            int nm = (element.second + v.second) % M;
            if (result[nm] == -1) {
                result[nm] = result[element.second] + v.first;
                queue.emplace(result[nm], nm);
            } else if (result[nm] > result[element.second] + v.first) {
                result[nm] = result[element.second] + v.first;
                queue.emplace(result[nm], nm);
            }
        }
    }

    for (int i=0; i<M; ++i) {
        printf("%lld\n", result[i]);
    }

    return 0;
}