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
/* 2024
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>

const int MAX_COLORS = 7001;
const int MAX_RANGE = 7001;
const long long int MAX_COST = 1llu << 62;

int types;
int colors;
int range;
int color;
int mass;
int cost;
long long int *result = nullptr;
long long int partial[MAX_COLORS][MAX_RANGE];
std::vector<std::pair<int, int>> jelly[MAX_COLORS];
std::vector<std::pair<int, long long int>> steps;
std::priority_queue<std::pair<long long int, int>> que;

void generate_initial_set(void);
void explore(void);

int main(void)
{
    scanf("%d %d %d", &types, &colors, &range);
    for(int t = 0; t < types; ++t)
    {
        scanf("%d %d %d", &color, &mass, &cost);
        jelly[color - 1].push_back({mass, cost});
    }

    result = partial[colors];
    for(int c = 0; c <= colors; ++c)
        for(int r = 0; r < range; ++r)
            partial[c][r] = MAX_COST;

    partial[0][0] = 0;
    generate_initial_set();
    result[0] = 0;
    explore();
    for(int r = 0; r < range; ++r)
        printf("%lld\n", result[r] != MAX_COST ? result[r] : -1);

    return 0;
}

inline void generate_initial_set(void)
{
    for(int c = 0; c < colors; ++c)
        for(int m = 0; m < range; ++m)
            for(auto &[jelly_mass, jelly_cost]: jelly[c])
                partial[c + 1][(m + jelly_mass) % range] = std::min(partial[c + 1][(m + jelly_mass) % range], partial[c][m] + jelly_cost);

    for(int r = 1; r < range; ++r)
        if(result[r] != MAX_COST)
        {
            steps.push_back({r, result[r]});
            que.push({-result[r], -r});
        }
}

inline void explore(void)
{
    while(!que.empty())
    {
        auto [current_cost, current_mass] = que.top();
        current_cost *= -1;
        current_mass *= -1;
        que.pop();
        if(result[current_mass] < current_cost)
            continue;

        for(auto &[step_mass, step_cost]: steps)
        {
            int next_mass = (current_mass + step_mass) % range;
            if(result[next_mass] <= result[current_mass] + step_cost)
                continue;

            result[next_mass] = result[current_mass] + step_cost;
            que.push({-result[next_mass], -next_mass});
        }
    }
}