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
93
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long

constexpr int maxn=7000+7;
constexpr ll inf=1e18;

int n,k,m;
int kolor,masa,wartosc;

pair<int,pair<int,int>>input[maxn];

vector<pair<int,ll>>vec;
//.f-nastepny .s-cena

ll solv[maxn];
ll dp[2][maxn];
void prepere()
{
    for(int i=0;i<maxn;++i)
        solv[i]=inf;
}

void Dijkstra()
{
    priority_queue<pair<ll,int>>pq;
    //.f=-cena .s=miejsce
    pq.push({0,0});

    while(!pq.empty())
    {
        auto top=pq.top();
        pq.pop();
        top.f=-top.f;

        //po wszystkich sasiadach
        for(auto &u: vec)//(top.s+u.f)%m <- destynacja
            if(solv[(top.s+u.f)%m]>top.f+u.s)
            {
                solv[(top.s+u.f)%m]=top.f+u.s;
                pq.push({-(top.f+u.s),(top.s+u.f)%m});
            }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k>>m;
    for(int i=1;i<=n;++i)
        cin>>input[i].f>>input[i].s.f>>input[i].s.s;
    sort(&input[1],&input[n+1]);

    prepere();
    dp[0][0]=0;
    for(int i=1;i<=m-1;++i)
        dp[0][i]=inf;

    int iter=0;
    for(int kol=1;kol<=k;++kol)
    {
        for(int i=0;i<=m-1;++i)
            dp[kol&1][i]=inf;
        while(iter+1<=n && input[iter+1].f==kol)
        {
            iter++;
            pair<int,int>v={input[iter].s.f, input[iter].s.s};
            for(int i=0;i<=m-1;i++)
                dp[kol&1][(i+v.f)%m] = min(dp[(kol-1)&1][i]+v.s, dp[kol&1][(i+v.f)%m]);
        }
    }
    // dp[k] <- mam zapisany najmniejszy koszt sciezki danej dlugosci

    for(int j=1;j<=m-1;++j)
        if(dp[k&1][j]<inf)
            vec.push_back({j,dp[k&1][j]});

    Dijkstra();
    cout<<"0\n";
    for(int i=1;i<=m-1;++i)
    {
        if(solv[i]==inf)
            cout<<"-1\n";
        else
            cout<<solv[i]<<'\n';
    }
    return 0;
}