TCO2012 Round2C Easy(300) 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; }};