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
94
95
96
97
98
#include <bits/stdc++.h>

using namespace std;

struct zelka{
    int masa;
    int cena;
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n,k,m,numer,mod;
    zelka pomoc;
    cin >> n >> k >> m;
    vector<vector<zelka>>v(k+1);
    for(long long i=0; i<n; i++){
        cin >> numer >> pomoc.masa >> pomoc.cena;
        v[numer].push_back(pomoc);
    }
    vector<long long>prefiksy(m+1,0);
    for(long long i=0; i<v[1].size();i++){
        if(prefiksy[v[1][i].masa]==0){
            prefiksy[v[1][i].masa] = v[1][i].cena;
        }else{
            if(prefiksy[v[1][i].masa]>v[1][i].cena){
                 prefiksy[v[1][i].masa] = v[1][i].cena;
            }
        }
    }
    for(long long i=2; i<v.size();i++){
        vector<long long>kopia(m+1,0);
        for(int j=0; j<v[i].size();j++){
            mod = v[i][j].masa+1;
            for(int z=1;z<=m;z++){
                if(mod>m)mod = mod -m;
                if(prefiksy[z]!=0){
                    if(kopia[mod]==0){
                        kopia[mod]= prefiksy[z] + v[i][j].cena;
                    }else{
                        if(kopia[mod]>prefiksy[z]+v[i][j].cena){
                            kopia[mod] = prefiksy[z]+v[i][j].cena;
                        }
                    }
                }
                mod++;
            }
        }
        prefiksy = kopia;
    }
    vector<pair<long long,bool>>wyniki(m+1);
    for(long long i=1; i<=m;i++){
        if(prefiksy[i]!=0){
            wyniki[i].first = prefiksy[i];
        }else{
            wyniki[i].first = 1000000000000000000;
        }
        wyniki[i].second = false;
    }
    wyniki[m].first = 0;
    wyniki[m].second = true;
    long long nrmini;
    for(long long i=1; i<m;i++){
        nrmini = 0;
        for(long long j=1; j<=m; j++){
            if(!wyniki[j].second){
                if(nrmini==0){
                    nrmini = j;
                }else{
                    if(wyniki[nrmini].first>wyniki[j].first){
                        nrmini = j;
                    }
                }
            }
        }
        wyniki[nrmini].second = true;
        mod = nrmini+1;
        for(int j=1; j<=m;j++){
            if(mod>m)mod = mod - m;
            if(wyniki[j].second){
                if(wyniki[mod].first > wyniki[j].first + wyniki[nrmini].first){
                    wyniki[mod].first = wyniki[j].first + wyniki[nrmini].first;
                }
            }
            mod++;
        }
    }
    cout << "0" << endl;
    for(long long i=1; i<m;i++){
        if(wyniki[i].first == 1000000000000000000){
            cout << "-1" << endl;
        }else{
            cout << wyniki[i].first << endl;
        }
    }
    return 0;
}