2573eaa216 2013-03-25        kinaba: #include <iostream>
2573eaa216 2013-03-25        kinaba: #include <sstream>
2573eaa216 2013-03-25        kinaba: #include <iomanip>
2573eaa216 2013-03-25        kinaba: #include <vector>
2573eaa216 2013-03-25        kinaba: #include <string>
2573eaa216 2013-03-25        kinaba: #include <map>
2573eaa216 2013-03-25        kinaba: #include <set>
2573eaa216 2013-03-25        kinaba: #include <algorithm>
2573eaa216 2013-03-25        kinaba: #include <numeric>
2573eaa216 2013-03-25        kinaba: #include <iterator>
2573eaa216 2013-03-25        kinaba: #include <functional>
2573eaa216 2013-03-25        kinaba: #include <complex>
2573eaa216 2013-03-25        kinaba: #include <queue>
2573eaa216 2013-03-25        kinaba: #include <stack>
2573eaa216 2013-03-25        kinaba: #include <cmath>
2573eaa216 2013-03-25        kinaba: #include <cassert>
2573eaa216 2013-03-25        kinaba: using namespace std;
2573eaa216 2013-03-25        kinaba: typedef long long LL;
2573eaa216 2013-03-25        kinaba: typedef long double LD;
2573eaa216 2013-03-25        kinaba: typedef complex<LD> CMP;
2573eaa216 2013-03-25        kinaba: 
2573eaa216 2013-03-25        kinaba: class SkiResorts { public:
2573eaa216 2013-03-25        kinaba: 	long long minCost(vector <string> road, vector <int> altitude)
2573eaa216 2013-03-25        kinaba: 	{
2573eaa216 2013-03-25        kinaba: 		typedef int Vert;
2573eaa216 2013-03-25        kinaba: 		typedef int Alt;
2573eaa216 2013-03-25        kinaba: 		typedef pair<Vert,Alt> State;
2573eaa216 2013-03-25        kinaba: 		typedef LL Cost;
2573eaa216 2013-03-25        kinaba: 		typedef pair<Cost,State> Edge;
2573eaa216 2013-03-25        kinaba: 		const int N = altitude.size();
2573eaa216 2013-03-25        kinaba: 
2573eaa216 2013-03-25        kinaba: 		priority_queue< Edge, vector<Edge>, greater<Edge> > Q;
2573eaa216 2013-03-25        kinaba: 		set<State> V;
2573eaa216 2013-03-25        kinaba: 		for(int i=0; i<N; ++i) {
2573eaa216 2013-03-25        kinaba: 			State init(0, altitude[i]);
2573eaa216 2013-03-25        kinaba: 			Q.push( Edge(abs(altitude[i]-altitude[0]), init) );
2573eaa216 2013-03-25        kinaba: 		}
2573eaa216 2013-03-25        kinaba: 		while( !Q.empty() ) {
2573eaa216 2013-03-25        kinaba: 			Cost  c = Q.top().first;
2573eaa216 2013-03-25        kinaba: 			State s = Q.top().second;
2573eaa216 2013-03-25        kinaba: 			Vert v  = s.first;
2573eaa216 2013-03-25        kinaba: 			Alt  vh = s.second;
2573eaa216 2013-03-25        kinaba: 			Q.pop();
2573eaa216 2013-03-25        kinaba: 			if( V.count(s) )
2573eaa216 2013-03-25        kinaba: 				continue;
2573eaa216 2013-03-25        kinaba: 			V.insert(s);
2573eaa216 2013-03-25        kinaba: 			if( v == N-1 )
2573eaa216 2013-03-25        kinaba: 				return c;
2573eaa216 2013-03-25        kinaba: 
2573eaa216 2013-03-25        kinaba: 			for(Vert u=0; u<N; ++u) if(road[v][u] =='Y') {
2573eaa216 2013-03-25        kinaba: 				Alt uh = altitude[u];
2573eaa216 2013-03-25        kinaba: 				for(int i=0; i<N; ++i) {
2573eaa216 2013-03-25        kinaba: 					Alt ch = altitude[i];
2573eaa216 2013-03-25        kinaba: 					if( ch <= vh ) {
2573eaa216 2013-03-25        kinaba: 						Cost cc = c + abs(ch-uh);
2573eaa216 2013-03-25        kinaba: 						State ss(u, ch);
2573eaa216 2013-03-25        kinaba: 						if(!V.count(ss))
2573eaa216 2013-03-25        kinaba: 							Q.push(Edge(cc,ss));
2573eaa216 2013-03-25        kinaba: 					}
2573eaa216 2013-03-25        kinaba: 				}
2573eaa216 2013-03-25        kinaba: 			}
2573eaa216 2013-03-25        kinaba: 		}
2573eaa216 2013-03-25        kinaba: 		return -1;
2573eaa216 2013-03-25        kinaba: 	}
2573eaa216 2013-03-25        kinaba: };
2573eaa216 2013-03-25        kinaba: 
2573eaa216 2013-03-25        kinaba: // BEGIN CUT HERE
2573eaa216 2013-03-25        kinaba: #include <ctime>
2573eaa216 2013-03-25        kinaba: double start_time; string timer()
2573eaa216 2013-03-25        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
2573eaa216 2013-03-25        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
2573eaa216 2013-03-25        kinaba:  { os << "{ ";
2573eaa216 2013-03-25        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
2573eaa216 2013-03-25        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
2573eaa216 2013-03-25        kinaba: void verify_case(const long long& Expected, const long long& Received) {
2573eaa216 2013-03-25        kinaba:  bool ok = (Expected == Received);
2573eaa216 2013-03-25        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
2573eaa216 2013-03-25        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
2573eaa216 2013-03-25        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
2573eaa216 2013-03-25        kinaba: #define END	 verify_case(_, SkiResorts().minCost(road, altitude));}
2573eaa216 2013-03-25        kinaba: int main(){
2573eaa216 2013-03-25        kinaba: CASE(0)
2573eaa216 2013-03-25        kinaba: 	string road_[] = {"NYN",
2573eaa216 2013-03-25        kinaba:  "YNY",
2573eaa216 2013-03-25        kinaba:  "NYN"};
2573eaa216 2013-03-25        kinaba: 	  vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
2573eaa216 2013-03-25        kinaba: 	int altitude_[] = {30, 20, 10};
2573eaa216 2013-03-25        kinaba: 	  vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
2573eaa216 2013-03-25        kinaba: 	long long _ = 0LL;
2573eaa216 2013-03-25        kinaba: END
2573eaa216 2013-03-25        kinaba: CASE(1)
2573eaa216 2013-03-25        kinaba: 	string road_[] = {"NY",
2573eaa216 2013-03-25        kinaba:  "YN"};
2573eaa216 2013-03-25        kinaba: 	  vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
2573eaa216 2013-03-25        kinaba: 	int altitude_[] = {10, 20};
2573eaa216 2013-03-25        kinaba: 	  vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
2573eaa216 2013-03-25        kinaba: 	long long _ = 10LL;
2573eaa216 2013-03-25        kinaba: END
2573eaa216 2013-03-25        kinaba: CASE(2)
2573eaa216 2013-03-25        kinaba: 	string road_[] = {"NYN",
2573eaa216 2013-03-25        kinaba:  "YNN",
2573eaa216 2013-03-25        kinaba:  "NNN"};
2573eaa216 2013-03-25        kinaba: 	  vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
2573eaa216 2013-03-25        kinaba: 	int altitude_[] = {573, 573, 573};
2573eaa216 2013-03-25        kinaba: 	  vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
2573eaa216 2013-03-25        kinaba: 	long long _ = -1LL;
2573eaa216 2013-03-25        kinaba: END
2573eaa216 2013-03-25        kinaba: CASE(3)
2573eaa216 2013-03-25        kinaba: 	string road_[] = {"NNYNNYYYNN",
2573eaa216 2013-03-25        kinaba:  "NNNNYNYNNN",
2573eaa216 2013-03-25        kinaba:  "YNNNNYYNNN",
2573eaa216 2013-03-25        kinaba:  "NNNNNNYNYY",
2573eaa216 2013-03-25        kinaba:  "NYNNNNNNYY",
2573eaa216 2013-03-25        kinaba:  "YNYNNNNYNN",
2573eaa216 2013-03-25        kinaba:  "YYYYNNNYNN",
2573eaa216 2013-03-25        kinaba:  "YNNNNYYNNN",
2573eaa216 2013-03-25        kinaba:  "NNNYYNNNNN",
2573eaa216 2013-03-25        kinaba:  "NNNYYNNNNN"};
2573eaa216 2013-03-25        kinaba: 	  vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
2573eaa216 2013-03-25        kinaba: 	int altitude_[] = {7, 4, 13, 2, 8, 1, 8, 15, 5, 15};
2573eaa216 2013-03-25        kinaba: 	  vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
2573eaa216 2013-03-25        kinaba: 	long long _ = 12LL;
2573eaa216 2013-03-25        kinaba: END
2573eaa216 2013-03-25        kinaba: CASE(4)
2573eaa216 2013-03-25        kinaba: 	string road_[] = {
2573eaa216 2013-03-25        kinaba: 		"NYNNNNNN",
2573eaa216 2013-03-25        kinaba: 		"YNYNNNNN",
2573eaa216 2013-03-25        kinaba: 		"NYNYNNNN",
2573eaa216 2013-03-25        kinaba: 		"NNYNYNNN",
2573eaa216 2013-03-25        kinaba: 		"NNNYNYNN",
2573eaa216 2013-03-25        kinaba: 		"NNNNYNYN",
2573eaa216 2013-03-25        kinaba: 		"NNNNNYNY",
2573eaa216 2013-03-25        kinaba: 		"NNNNNNYN"
2573eaa216 2013-03-25        kinaba: 	};
2573eaa216 2013-03-25        kinaba: 	  vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
2573eaa216 2013-03-25        kinaba: 	  int altitude_[] = {
2573eaa216 2013-03-25        kinaba: 		  1,2,3,3,3,3,3,3
2573eaa216 2013-03-25        kinaba: 	  };
2573eaa216 2013-03-25        kinaba: 	  vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
2573eaa216 2013-03-25        kinaba: 	long long _ = 3LL;
2573eaa216 2013-03-25        kinaba: END
2573eaa216 2013-03-25        kinaba: /*
2573eaa216 2013-03-25        kinaba: CASE(5)
2573eaa216 2013-03-25        kinaba: 	string road_[] = ;
2573eaa216 2013-03-25        kinaba: 	  vector <string> road(road_, road_+sizeof(road_)/sizeof(*road_));
2573eaa216 2013-03-25        kinaba: 	int altitude_[] = ;
2573eaa216 2013-03-25        kinaba: 	  vector <int> altitude(altitude_, altitude_+sizeof(altitude_)/sizeof(*altitude_));
2573eaa216 2013-03-25        kinaba: 	long long _ = LL;
2573eaa216 2013-03-25        kinaba: END
2573eaa216 2013-03-25        kinaba: */
2573eaa216 2013-03-25        kinaba: }
2573eaa216 2013-03-25        kinaba: // END CUT HERE