如题

//SIXIANG
#include <iostream>
#include <algorithm>
#define M 10
#define N 100
#define QWQ cout << "QWQ" << endl;
using namespace std;
int f[M + 10][N + 10], a[M + 10][N + 10], n, m, path[M + 10][N + 10];
void opath(int x, int y) {
	if(y == m) {
		cout << x;
		return ;
	}
	cout << x << ' ';
	opath(path[x][y], y + 1);
} 
void init() {
	for(int p = 1; p <= n; p++)
		for(int i = 1; i <= m; i++)
			cin >> a[p][i];
	
	for(int p = 1; p <= n; p++) 
		for(int i = 1; i <= m; i++)
			f[p][i] = 0x3f3f3f3f, path[p][i] = 0;
	
	for(int p = 1; p <= n; p++) f[p][m] = a[p][m];
	for(int j = m; j >= 1; j--) {
		for(int i = 1; i <= n; i++) {
			int nj = ((j == 1) ? (m) : (j - 1));
			int tmp[3] = {i, i - 1, i + 1};
			
			if(!(i - 1)) tmp[1] = n;
			if((i + 1) > n) tmp[2] = 1;
			sort(tmp, tmp + 3);
			
			for(int p = 0; p < 3; p++) {
				if(f[i][j] + a[tmp[p]][nj] < f[tmp[p]][nj]) {
					f[tmp[p]][nj] = f[i][j] + a[tmp[p]][nj];
					path[tmp[p]][nj] = i;
				}
			}
		}
	}
	int minn = 1145141919, line;
	for(int p = 1; p <= n; p++)
		if(f[p][1] < minn) {
			minn = f[p][1];
			line = p;
		}
	
	opath(line, 1);
	cout << endl << minn << endl;
}
int main() {
	while(cin >> n >> m)
		init();
}

一直调不对 QAQ

udebug 都过了，求 hack