1. C++, Evgeni Pavlidis

/**
* ACM programming Contest WS 08/09
* UVa Status: accepted
* Run Time: 0.640
* Category: Dynamic Programming
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
#include <iostream>
#include <sstream>
#include <climits>

using namespace std;

int m[100][10];
int save[100][10];
int rows,cols;

string printResult(int c, int r)
{
if(c == cols-1)
return "";
stringstream out;
out << save[c][r]+1;
return " " + out.str() + printResult(c+1, save[c][r]);
}

int main()
{

while(true)
{
cin >> rows;
cin >> cols;
if(feof(stdin))
return 0;

for(int r=0; r < rows; r++)
for(int c=0; c < cols; c++)
cin >> m[c][r];

int prev,next,middle,min;

for(int c=cols-2; c >= 0; c--)
for(int r=0; r < rows; r++)
{
if(r==0)
{
next = rows-1;
prev = r;
middle = r+1;
}
else if(r==rows-1)
{
next = r;
prev = 0;
middle = r-1;
}
else
{
next = r+1;
middle = r;
prev = r-1;
}

if(rows == 1)
{
next = 0;
middle = 0;
prev = 0;
}

min = (m[c+1][prev] <= m[c+1][middle] )? prev : middle;
min = (m[c+1][min] <= m[c+1][next])? min : next;
m[c][r] = m[c+1][min] + m[c][r];
save[c][r] = min;
}


int mini = INT_MAX, saveRow=0;
for(int r=0; r < rows; r++)
if(m[0][r] < mini)
{
mini = m[0][r];
saveRow = r;
}

cout << saveRow+1 << printResult(0,saveRow) << endl;
cout << mini << endl;

}
}