The input file contains several test cases, each of them as described below.
- The first line of the input contains two integers N,M (2 ≤ N≤ 100000, 1 ≤ M≤ 100), giving the length of vacation and the T-shirts that JSZKC has.
- The next follows M lines with each line M integers. The jth integer in the ith line means f[i][j](1<=f[i][j]<=1000000).
There are no more than 10 test cases.
#include <bits/stdc++.h>
#define maxn 105
using namespace std;
typedef long long ll;
ll f[25][maxn][maxn]={0};
ll ans[2][maxn][maxn]={0};
int main()
{
int n,m,i,j,k,l;
while(~scanf("%d%d",&n,&m))
{
memset(f,0,sizeof(f));
memset(ans,0,sizeof(ans));
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++)
{
scanf("%lld",&f[0][i][j]);
}
}
for(i=1;i<=20;i++)
{
for(j=1;j<=m;j++)
{
for(k=1;k<=m;k++)
{
for(l=1;l<=m;l++)
{
f[i][j][k]=max(f[i][j][k],f[i-1][j][l]+f[i-1][l][k]);
}
}
}
}
n--;
int temp=1;
for(i=0;i<=20;i++)
{
if(n&(1<<i))
{
for(j=1;j<=m;j++)
{
for(k=1;k<=m;k++)
{
for(l=1;l<=m;l++)
{
ans[temp][j][k]=max(ans[temp][j][k],ans[1-temp][j][l]+f[i][l][k]);
}
}
}
temp=1-temp;
}
}
temp=1-temp;
ll maxim=0;
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++)
{
maxim=max(ans[temp][i][j],maxim);
}
}
cout<<maxim<<endl;
}
return 0;
}
