UVa 116 - Unidirectional TSP

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%lld",&a)
#define sii(a,b) scanf("%lld %lld",&a,&b)
#define siii(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

ll k,n,m,a[105][105],dp[105][105],b[105][105];

vector<ll> w[105];

int cmp(pair<ll,ll> p,pair<ll,ll> q){
    if(p.first!=q.first)
        return p.first<q.first;
    return p.second<q.second;
}

void solve(ll i,ll j){
    if(b[i][j]!=-1){
        w[k].pb(b[i][j]);
        solve(b[i][j],j+1);
    }
}

int main(){
    ll r,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    while(sii(n,m)!=EOF){
        clr(dp,0);
        f(i,0,n)
            f(j,0,m)
                si(a[i][j]);
        f(i,0,n){
            dp[i][m-1]=a[i][m-1];
            b[i][m-1]=-1;
        }
        rf(j,m-2,0){
            f(i,0,n){
                vector<pair<ll,ll> > v;
                dp[i][j]=a[i][j];
                ll ll=(i-1+n)%n,rr=(i+1)%n;
                x=dp[i][j+1];y=dp[ll][j+1];z=dp[rr][j+1];
                v.pb(mp(x,i));v.pb(mp(y,ll));v.pb(mp(z,rr));
                sort(all(v),cmp);
                dp[i][j]+=v[0].first;
                b[i][j]=v[0].second;
            }
        }

        z=LONG_LONG_MAX;
        f(i,0,n)
            z=min(z,dp[i][0]);
        k=0;
        f(i,0,n){
            if(dp[i][0]==z){
                w[k].pb(i);
                solve(i,0);
                k++;
            }
        }
        x=0;
        f(i,0,k){
            c=0;
            f(j,0,k){
                f(l,0,m){
                    if(w[i][l]!=w[j][l]){
                        if(w[i][l]<w[j][l])
                            c++;
                        break;
                    }

                }
                if(c==k-1)
                    break;
            }
            if(c==k-1)
                break;
        }
        f(j,0,m)
            if(j!=m-1)
                cout<<w[i][j]+1<<" ";
            else
                cout<<w[i][j]+1<<endl;
        cout<<z<<endl;
        f(i,0,k)
            w[i].clear();
    }

    return 0;
}