50077c1ac1 2014-05-29 kinaba: #include <iostream> 50077c1ac1 2014-05-29 kinaba: #include <sstream> 50077c1ac1 2014-05-29 kinaba: #include <iomanip> 50077c1ac1 2014-05-29 kinaba: #include <vector> 50077c1ac1 2014-05-29 kinaba: #include <string> 50077c1ac1 2014-05-29 kinaba: #include <map> 50077c1ac1 2014-05-29 kinaba: #include <set> 50077c1ac1 2014-05-29 kinaba: #include <algorithm> 50077c1ac1 2014-05-29 kinaba: #include <numeric> 50077c1ac1 2014-05-29 kinaba: #include <iterator> 50077c1ac1 2014-05-29 kinaba: #include <functional> 50077c1ac1 2014-05-29 kinaba: #include <complex> 50077c1ac1 2014-05-29 kinaba: #include <queue> 50077c1ac1 2014-05-29 kinaba: #include <stack> 50077c1ac1 2014-05-29 kinaba: #include <cmath> 50077c1ac1 2014-05-29 kinaba: #include <cassert> 50077c1ac1 2014-05-29 kinaba: #include <tuple> 50077c1ac1 2014-05-29 kinaba: using namespace std; 50077c1ac1 2014-05-29 kinaba: typedef long long LL; 50077c1ac1 2014-05-29 kinaba: typedef complex<double> CMP; 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: class BuildingRoutes { public: 50077c1ac1 2014-05-29 kinaba: int build(vector <string> dist, int T) 50077c1ac1 2014-05-29 kinaba: { 50077c1ac1 2014-05-29 kinaba: const int N = dist.size(); 50077c1ac1 2014-05-29 kinaba: vector<vector<int>> use(N, vector<int>(N, 0)); 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: vector<vector<int>> d(N, vector<int>(N)); 50077c1ac1 2014-05-29 kinaba: for(int s=0; s<N; ++s) 50077c1ac1 2014-05-29 kinaba: for(int t=0; t<N; ++t) 50077c1ac1 2014-05-29 kinaba: d[s][t] = dist[s][t] - '0'; 50077c1ac1 2014-05-29 kinaba: for(int k=0; k<N; ++k) 50077c1ac1 2014-05-29 kinaba: for(int i=0; i<N; ++i) 50077c1ac1 2014-05-29 kinaba: for(int j=0; j<N; ++j) 50077c1ac1 2014-05-29 kinaba: d[i][j] = min(d[i][j], d[i][k]+d[k][j]); 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: for(int s=0; s<N; ++s) 50077c1ac1 2014-05-29 kinaba: for(int t=0; t<N; ++t) 50077c1ac1 2014-05-29 kinaba: for(int a=0; a<N; ++a) 50077c1ac1 2014-05-29 kinaba: for(int b=0; b<N; ++b) if(a!=b) 50077c1ac1 2014-05-29 kinaba: if(d[s][a]+(dist[a][b]-'0')+d[b][t] == d[s][t]) 50077c1ac1 2014-05-29 kinaba: use[a][b] ++; 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: int total = 0; 50077c1ac1 2014-05-29 kinaba: for(int s=0; s<N; ++s) 50077c1ac1 2014-05-29 kinaba: for(int t=0; t<N; ++t) 50077c1ac1 2014-05-29 kinaba: if(use[s][t] >= T) 50077c1ac1 2014-05-29 kinaba: total += dist[s][t] - '0'; 50077c1ac1 2014-05-29 kinaba: return total; 50077c1ac1 2014-05-29 kinaba: } 50077c1ac1 2014-05-29 kinaba: }; 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: // BEGIN CUT HERE 50077c1ac1 2014-05-29 kinaba: #include <ctime> 50077c1ac1 2014-05-29 kinaba: double start_time; string timer() 50077c1ac1 2014-05-29 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 50077c1ac1 2014-05-29 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 50077c1ac1 2014-05-29 kinaba: { os << "{ "; 50077c1ac1 2014-05-29 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 50077c1ac1 2014-05-29 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 50077c1ac1 2014-05-29 kinaba: void verify_case(const int& Expected, const int& Received) { 50077c1ac1 2014-05-29 kinaba: bool ok = (Expected == Received); 50077c1ac1 2014-05-29 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 50077c1ac1 2014-05-29 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 50077c1ac1 2014-05-29 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 50077c1ac1 2014-05-29 kinaba: #define END verify_case(_, BuildingRoutes().build(dist, T));} 50077c1ac1 2014-05-29 kinaba: int main(){ 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: CASE(0) 50077c1ac1 2014-05-29 kinaba: string dist_[] = {"011", 50077c1ac1 2014-05-29 kinaba: "101", 50077c1ac1 2014-05-29 kinaba: "110"}; 50077c1ac1 2014-05-29 kinaba: vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int T = 1; 50077c1ac1 2014-05-29 kinaba: int _ = 6; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: CASE(1) 50077c1ac1 2014-05-29 kinaba: string dist_[] = {"033", 50077c1ac1 2014-05-29 kinaba: "309", 50077c1ac1 2014-05-29 kinaba: "390"}; 50077c1ac1 2014-05-29 kinaba: vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int T = 1; 50077c1ac1 2014-05-29 kinaba: int _ = 12; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: CASE(2) 50077c1ac1 2014-05-29 kinaba: string dist_[] = {"0123", 50077c1ac1 2014-05-29 kinaba: "1023", 50077c1ac1 2014-05-29 kinaba: "1203", 50077c1ac1 2014-05-29 kinaba: "1230"}; 50077c1ac1 2014-05-29 kinaba: vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int T = 2; 50077c1ac1 2014-05-29 kinaba: int _ = 5; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: CASE(3) 50077c1ac1 2014-05-29 kinaba: string dist_[] = {"05789654", 50077c1ac1 2014-05-29 kinaba: "10347583", 50077c1ac1 2014-05-29 kinaba: "65085479", 50077c1ac1 2014-05-29 kinaba: "55602398", 50077c1ac1 2014-05-29 kinaba: "76590934", 50077c1ac1 2014-05-29 kinaba: "57939045", 50077c1ac1 2014-05-29 kinaba: "12345608", 50077c1ac1 2014-05-29 kinaba: "68647640"}; 50077c1ac1 2014-05-29 kinaba: vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int T = 3; 50077c1ac1 2014-05-29 kinaba: int _ = 40; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: /* 50077c1ac1 2014-05-29 kinaba: CASE(4) 50077c1ac1 2014-05-29 kinaba: string dist_[] = ; 50077c1ac1 2014-05-29 kinaba: vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int T = ; 50077c1ac1 2014-05-29 kinaba: int _ = ; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: CASE(5) 50077c1ac1 2014-05-29 kinaba: string dist_[] = ; 50077c1ac1 2014-05-29 kinaba: vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int T = ; 50077c1ac1 2014-05-29 kinaba: int _ = ; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: */ 50077c1ac1 2014-05-29 kinaba: } 50077c1ac1 2014-05-29 kinaba: // END CUT HERE