Untitled
unknown
plain_text
6 months ago
1.1 kB
0
Indexable
Never
#include <iostream> #define N 101 #define oo 2000000 using namespace std; int ans; int m,d; int doigiay(int u, int v) { return u*60+v; } int min(int u, int v) { if(u>v)return v; return u; } int tim[N],en[N]; int f[N][10000]; void doc() { cin>>m>>d; int u,v; for(int i=0;i<=d;i++) for(int j=0;j<=m;j++)f[i][j]=oo; for(int i=1;i<=5;i++) { cin>>u>>v>>en[i]; tim[i]=doigiay(u,v); f[1][en[i]]=min(f[1][en[i]],tim[i]); } for(int i=1;i<=d;i++) for(int j=1;j<=m;j++)if(f[i][j]!=oo) { for(int ii=1;ii<=5;ii++) { if(j+en[ii]<=m) { f[i+1][j+en[ii]]=min(f[i+1][j+en[ii]],f[i][j]+tim[ii]); //if(time[ii]==20&&j%17==0)cout<<i+1<<" "<<j+en[ii]<<" "<<f[i+1][j+en[ii]]<<"\n"; } } } ans=oo; int nl; for(int i=1;i<=m;i++) { ans=min(ans,f[d][i]); } } int main() { freopen("input.txt","r",stdin); int TC; cin>>TC; for(int tc=1;tc<=TC;tc++) { doc(); cout<<"Case #"<<tc<<"\n"; if(ans==oo)cout<<-1<<"\n";else { cout<<ans/60<<" "<<ans%60<<"\n"; } //cout<<ans<<"\n"; } return 0; }