zoj3017.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <stdio.h>
#include <string.h>

int tm[20][110], mg[20][20];
int f[110][20][110];
int n, m, z;
int main(){
	int cases;  scanf("%d", &cases);
	while (cases--){
		scanf("%d%d%d", &n, &m, &z);
		for (int i = 1; i <= m; i++)
			for (int j = 2; j <= n; j++)
				scanf("%d", &tm[i][j]);
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= m; j++)
				scanf("%d",&mg[i][j]);
		for (int k = 1; k <= m; k++)
			for (int i = 1; i <= m; i++)
				for (int j = 1; j <= m; j++)
					if (mg[i][k] + mg[k][j] < mg[i][j])
						mg[i][j] = mg[i][k] + mg[k][j];
		memset(f, 0xff, sizeof(f));
		f[z][1][1] = 0;
		for (int i = 2; i <= m; i++)
			if (z - mg[1][i] >= 0) f[z - mg[1][i]][i][1] = 0;
		for (int j = 1; j < n; j++)
			for (int k = 0; k <= z; k++)
				for (int i = 1; i <= m; i++) if (f[k][i][j] != -1){
					int t = j + 1, tmp = f[k][i][j] + tm[i][t], nmg;
					if (f[k][i][t] == -1 || tmp < f[k][i][t])
						f[k][i][t] = tmp;
					for (int p = 1; p <= m; p++) if (p != i){
						if ((nmg = k - mg[i][p]) < 0) continue;
						tmp = f[k][i][j] + tm[p][t];
						if (f[nmg][p][t] == -1 || tmp < f[nmg][p][t])
							f[nmg][p][t] = tmp;
					}
				}
		int ans = 0x3fffffff;
		for (int i = 1; i <= m; i++)
			for (int k = 0; k <= z; k++) if (f[k][i][n] != -1){
				if (f[k][i][n] < ans) ans = f[k][i][n];
			}
		printf("%d\n", ans);
	}
	return 0;
}