#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
static const int INF = 0x3fffffff;
class TaxiManager { public:
int schedule(vector <string> roads, vector <string> customers)
{
const int V = roads.size();
vector< vector<int> > d(V, vector<int>(V));
for(int i=0; i<V; ++i)
for(int j=0; j<V; ++j)
if( i != j )
d[i][j] = (roads[i][j]=='0' ? INF : roads[i][j]-'0');
for(int k=0; k<V; ++k)
for(int i=0; i<V; ++i)
for(int j=0; j<V; ++j)
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
const int M = customers.size();
vector< pair<int,int> > c;
for(int i=0; i<M; ++i)
{
int f, t;
stringstream(customers[i]) >> f >> t;
c.push_back( make_pair(f,t) );
}
int best = INF;
for(int mask=0; mask<(1<<M); ++mask)
best = min(best, max(tsp(d,c,mask), tsp(d,c,((1<<M)-1)&~mask)));
return best;
}
map<pair<int,int>, int> memo;
int tsp(const vector< vector<int> >& d, const vector< pair<int,int> >& c, int mask, int cur=0)
{
if( mask == 0 )
return d[cur][0];
pair<int,int> key(mask, cur);
if( memo.count(key) ) return memo[key];
int best = INF;
for(int next=0; (1<<next)<=mask; ++next)
if( (1<<next) & mask )
best = min(best,
d[cur][c[next].first] + d[c[next].first][c[next].second] + tsp(d,c,mask&~(1<<next),c[next].second));
return memo[key] = best;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, TaxiManager().schedule(roads, customers));}
int main(){
CASE(0)
string roads_[] = {"020200"
,"202020"
,"020002"
,"200020"
,"020202"
,"002020"};
vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
string customers_[] = {"5 3","2 4","1 5","3 2"};
vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
int _ = 16;
END
CASE(1)
string roads_[] =
{"00020251090265906661"
,"00763002550100090081"
,"06003699000080062771"
,"00000710460400035310"
,"50000039119198350060"
,"66060004050810046028"
,"02333108565000200880"
,"40212560000209205231"
,"02601150098329905062"
,"00210383709951005203"
,"10111087340780827070"
,"05065800003095040140"
,"15604020082000100090"
,"83430030070580600750"
,"10588355007006001150"
,"14400080790005400536"
,"23400990400933060004"
,"11053016300602000090"
,"90040920084059282502"
,"61300007077904050900"};
vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
string customers_[] = {"0 19","4 16","15 16","4 18","2 7","9 15","11 6","7 13","19 13","12 19","14 12","16 1"};
vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
int _ = 33;
END
CASE(2)
string roads_[] =
{"095222800320504"
,"107600288090501"
,"760973530769345"
,"963093337510830"
,"338404069255826"
,"291700050155264"
,"002783031709004"
,"404730701707712"
,"068870030090995"
,"320025180036103"
,"468695042801904"
,"233626561000105"
,"070014432197086"
,"887301000143802"
,"230852749990330"};
vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
string customers_[] = {"3 6","0 4","2 7","9 7","13 9","1 6","7 13","14 2","8 7","10 1","11 13","7 12"};
vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
int _ = 28;
END
CASE(3)
string roads_[] = {"00401","50990","00062","08008","03000"};
vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
string customers_[] = {"2 4"};
vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
int _ = 14;
END
/*
CASE(4)
string roads_[] = ;
vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
string customers_[] = ;
vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
int _ = ;
END
CASE(5)
string roads_[] = ;
vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_));
string customers_[] = ;
vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_));
int _ = ;
END
*/
}
// END CUT HERE