#include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define sz(x) (int)((x).size()) #define int ll //#define N using namespace std; const int N=7005; int n,K,m; int tmp[N],dis[N]; bool vis[N]; vector<pa>G[N]; void BellaKira() { cin>>n>>K>>m; for (int i=1;i<=n;i++) { int x,y,z; cin>>x>>y>>z; G[x].push_back(mp(y,z)); } for (int i=0;i<m;i++) dis[i]=inf; dis[0]=0; for (int i=1;i<=K;i++) { for (int j=0;j<m;j++) tmp[j]=inf; for (auto [x,y]:G[i]) { for (int j=0;j<m;j++) tmp[(j+x)%m]=min(tmp[(j+x)%m],dis[j]+y); } for (int j=0;j<m;j++) dis[j]=tmp[j]; } dis[0]=0; for (int t=0;t<m;t++) { int now=-1; for (int i=0;i<m;i++) if (!vis[i]&&(now==-1||dis[i]<dis[now])) now=i; vis[now]=1; for (int i=0;i<m;i++) dis[i]=min(dis[i],dis[now]+dis[(i-now+m)%m]); } for (int i=0;i<m;i++) if (dis[i]==inf) cout<<"-1\n"; else cout<<dis[i]<<'\n'; } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } }
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 | #include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define sz(x) (int)((x).size()) #define int ll //#define N using namespace std; const int N=7005; int n,K,m; int tmp[N],dis[N]; bool vis[N]; vector<pa>G[N]; void BellaKira() { cin>>n>>K>>m; for (int i=1;i<=n;i++) { int x,y,z; cin>>x>>y>>z; G[x].push_back(mp(y,z)); } for (int i=0;i<m;i++) dis[i]=inf; dis[0]=0; for (int i=1;i<=K;i++) { for (int j=0;j<m;j++) tmp[j]=inf; for (auto [x,y]:G[i]) { for (int j=0;j<m;j++) tmp[(j+x)%m]=min(tmp[(j+x)%m],dis[j]+y); } for (int j=0;j<m;j++) dis[j]=tmp[j]; } dis[0]=0; for (int t=0;t<m;t++) { int now=-1; for (int i=0;i<m;i++) if (!vis[i]&&(now==-1||dis[i]<dis[now])) now=i; vis[now]=1; for (int i=0;i<m;i++) dis[i]=min(dis[i],dis[now]+dis[(i-now+m)%m]); } for (int i=0;i<m;i++) if (dis[i]==inf) cout<<"-1\n"; else cout<<dis[i]<<'\n'; } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } } |