zoj 3017 Extreme Gameplay

zoj 3017 Extreme Gameplay

#include <stdio.h>#include <string.h>#include<algorithm>using namespace std;const int maxn = 105;const int maxm = 15;int mat[maxm][maxn]; int dp[maxn][maxm][maxn];int map[maxm][maxm];int n,m,z;void init(){memset(dp , 0x3f, sizeof(dp));dp[0][0][z] = 0; for(int i = 1;i < m;i ++){ if(z >= map[0][i])dp[0][i][z - map[0][i]] = 0; } return ;}void solve(){init();for(int k=1; k<n; k++){for(int i=0; i<m; i++){for(int j=0; j<=z; j++){ for(int l = 0; l< m; l++) { if(i == l) { dp[k][i][j] = min(dp[k][i][j], dp[k - 1][i][j]); } else { if(j + map[l][i] <= z)dp[k][i][j] = min(dp[k][i][j], dp[k - 1][l][j + map[l][i]]); } }  dp[k][i][j] += mat[i][k-1]; }}}int ans = 0x3f3f3f3f;for(int i=0; i<m; i++)for(int j=0; j<=z; j++){if(ans > dp[n-1][i][j]) ans = dp[n-1][i][j];}printf("%dn",ans);}void floyd(){ for(int k=0; k<m; k++) for(int i=0; i<m; i++) for(int j=0; j<m ;j++) { if(map[i][k] + map[k][j] < map[i][j]) { map[i][j] = map[i][k] + map[k][j] ; } } }int main(){int T;scanf("%d", &T);while(T --){scanf("%d%d%d", &n, &m, &z);for(int i=0; i<m ;i++){for(int j=0; j<n-1; j++){scanf("%d", &mat[i][j]);}}for(int i=0; i<m; i++)for(int j=0; j<m; j++){scanf("%d", &map[i][j]);} floyd();solve();}}