#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; typedef long long ll; #define MAXN 7100 #define st first #define nd second int n,m,k; ll mem[MAXN][MAXN]; ll mem2[MAXN]; // unordered_map<int, unordered_map<int, unordered_map<int,ll>>> mem2; vector<pii> zel[MAXN]; ll f1(int r, int c) { if(c == -1) { if(r == 0) return 0; else return -1; } if(mem[r][c]!=0) return mem[r][c]; ll mi = LLONG_MAX; for(pii p:zel[c]) { ll res = f1((m+r-p.first)%m, c-1); if(res!=-1) mi = min(mi, res+p.second); } if(mi == LLONG_MAX) return mem[r][c]=-1; return mem[r][c]=mi; } // ll f2(int r, int c) // { // if(mem2[r][c]!=0) // return mem2[r][c]; // if(c == 0) // { // if(r == 0) // return 0; // return -1; // } // ll mi = LLONG_MAX; // ll sth = f2(r, c-1); // if(sth!=-1) // mi = sth; // for(int i=1; i<m; i++) // { // ll res = f1(i, k-1); // ll res2 = f2((m + r - i)%m, c - 1); // if(res!=-1&&res2!=-1) // mi = min(mi, res+res2); // } // // cout<<r<<" "<<c<<" "<<mi<<"\n"; // if(mi == LLONG_MAX) // return mem2[r][c]=-1; // return mem2[r][c]=mi; // } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k>>m; for(int i=0; i<n; i++) { int x,y,z; cin>>x>>y>>z; zel[x-1].push_back({y,z}); } // for(int i=-1; i<k; i++) // { // for(int j=0; j<m; j++) // cout<<f1(j, i)<<" "; // cout<<"\n"; // } // cout<<"\n\n"; // for(int i=0; i<k; i++) // { // for(int j=0; j<m; j++) // cout<<f2(j, i)<<" "; // cout<<"\n"; // } mem2[0] = 0; for(int i=1; i<m; i++) mem2[i] = LLONG_MAX; for(int i=1; i<m; i++) { ll r = f1(i, k-1); // cout<<i<<" "<<r<<"\n"; if(r!=-1) for(int j=0; j<m; j++) for(int mult = 1; mult<=m; mult++) { if(mem2[j%m]!=LLONG_MAX&&mem2[j%m]+r*mult<mem2[(j+i*mult)%m]) mem2[(j+i*mult)%m] = mem2[j%m]+r*mult; else break; } // for(int j=0; j<m; j++) // { // cout<<mem2[j]<<" "; // } // cout<<"\n"; } for(int i=0; i<m; i++) { if(mem2[i]!=LLONG_MAX) cout<<mem2[i]<<"\n"; else cout<<"-1\n"; } }
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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | #include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; typedef long long ll; #define MAXN 7100 #define st first #define nd second int n,m,k; ll mem[MAXN][MAXN]; ll mem2[MAXN]; // unordered_map<int, unordered_map<int, unordered_map<int,ll>>> mem2; vector<pii> zel[MAXN]; ll f1(int r, int c) { if(c == -1) { if(r == 0) return 0; else return -1; } if(mem[r][c]!=0) return mem[r][c]; ll mi = LLONG_MAX; for(pii p:zel[c]) { ll res = f1((m+r-p.first)%m, c-1); if(res!=-1) mi = min(mi, res+p.second); } if(mi == LLONG_MAX) return mem[r][c]=-1; return mem[r][c]=mi; } // ll f2(int r, int c) // { // if(mem2[r][c]!=0) // return mem2[r][c]; // if(c == 0) // { // if(r == 0) // return 0; // return -1; // } // ll mi = LLONG_MAX; // ll sth = f2(r, c-1); // if(sth!=-1) // mi = sth; // for(int i=1; i<m; i++) // { // ll res = f1(i, k-1); // ll res2 = f2((m + r - i)%m, c - 1); // if(res!=-1&&res2!=-1) // mi = min(mi, res+res2); // } // // cout<<r<<" "<<c<<" "<<mi<<"\n"; // if(mi == LLONG_MAX) // return mem2[r][c]=-1; // return mem2[r][c]=mi; // } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k>>m; for(int i=0; i<n; i++) { int x,y,z; cin>>x>>y>>z; zel[x-1].push_back({y,z}); } // for(int i=-1; i<k; i++) // { // for(int j=0; j<m; j++) // cout<<f1(j, i)<<" "; // cout<<"\n"; // } // cout<<"\n\n"; // for(int i=0; i<k; i++) // { // for(int j=0; j<m; j++) // cout<<f2(j, i)<<" "; // cout<<"\n"; // } mem2[0] = 0; for(int i=1; i<m; i++) mem2[i] = LLONG_MAX; for(int i=1; i<m; i++) { ll r = f1(i, k-1); // cout<<i<<" "<<r<<"\n"; if(r!=-1) for(int j=0; j<m; j++) for(int mult = 1; mult<=m; mult++) { if(mem2[j%m]!=LLONG_MAX&&mem2[j%m]+r*mult<mem2[(j+i*mult)%m]) mem2[(j+i*mult)%m] = mem2[j%m]+r*mult; else break; } // for(int j=0; j<m; j++) // { // cout<<mem2[j]<<" "; // } // cout<<"\n"; } for(int i=0; i<m; i++) { if(mem2[i]!=LLONG_MAX) cout<<mem2[i]<<"\n"; else cout<<"-1\n"; } } |