TCO2012 Round2C Easy(300) GreedyTravelingSalesman

GreedyTravelingSalesman

街iから街jへの道の工事後の長さで意味があるのは、街iから他の街への距離と±1、および9999のみ。全部試せば良い。

#include <string>
#include <vector>
#include <set>
using namespace std;

int n;
vector<vector<int> > D;
vector<bool> V;

int BT( int p )
{
    V[p] = true;

    int t = -1;
    for ( int i=0; i<n; i++ )
    if ( !V[i] )
        if ( t==-1 || D[p][i]<D[p][t] )
            t = i;

    int ans = t!=-1 ? BT(t)+D[p][t] : 0;

    V[p] = false;

    return ans;
}

class GreedyTravelingSalesman{public:
int worstDistance( vector <string> thousands, vector <string> hundreds, vector <string> tens, vector <string> ones )
{
    n = (int)thousands.size();
    
    D = vector<vector<int> >(n,vector<int>(n));
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<n; j++ )
        D[i][j] = (thousands[i][j]-'0')*1000
                + (hundreds[i][j]-'0')*100
                + (tens[i][j]-'0')*10
                + (ones[i][j]-'0')*1;
    V = vector<bool>(n);

    int ans = 0;

    for ( int i=0; i<n; i++ )
    for ( int j=0; j<n; j++ )
    if ( i!=j )
    {
        set<int> L;
        for ( int k=0; k<n; k++ )
        if ( k!=i )
        {
            if ( D[i][k]-1>=1 )
                L.insert(D[i][k]-1);
            L.insert(D[i][k]);
            if ( D[i][k]+1<=9999 )
                L.insert(D[i][k]+1);
        }
        L.insert(9999);
        
        for ( set<int>::iterator it=L.begin();
              it!=L.end(); it++ )
        {
            int t = D[i][j];
            D[i][j] = *it;

            ans = max( ans, BT(0) );

            D[i][j] = t;
        }
    }

    return ans;
}};