CheapestRoute.cpp

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cassert>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iterator>
#include <fstream>
using namespace std;

typedef long long 		int64;
typedef vector<int> 		vi;
typedef string 			ST;
typedef stringstream 		SS;
typedef vector< vector<int> > 	vvi;
typedef pair<int,int> 		ii;
typedef vector<string> 		vs;
/*
#if __cplusplus > 199711L	// for g++0x, value of __cplusplus must be greater thana 199711L.
	#define tr(i, c)	for(auto i = begin(c); i != end(c); i++)
#else
	#define tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#endif
*/
#define endl		("\n")
#define tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define PI		M_PI
#define E 		M_E
#define	eps		1e-9

#define	Sf		scanf
#define	Pf		printf

#define forn(i, n)	for(int i = 0, lets_stop_here = (int)n; i <  lets_stop_here; i++)
#define forab(i, a, b)	for(int i = a, lets_stop_here = (int)b; i <= lets_stop_here; i++)
#define rep(i, a, b)	for(int i = a, lets_stop_here = (int)b; i >= lets_stop_here; i--)

#define	all(c)		(c).begin(), (c).end()
#define	cl(a, b)	memset(a, b, sizeof(a))
#define mp		make_pair
#define pb		push_back

#define	present(x, c)	((c).find(x) != (c).end())	//map & set//
#define	cpresent(x, c)	(find( (c).begin(), (c).end(), x) != (c).end())	//vector & list//

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)

//#define debug(x)
#define debug(x)	cout << #x << " = " << x << "\n"

class CheapestRoute
{
public:
	vector <int> routePrice(vector <int> cellPrice, vector <int> enterCell, vector <int> exitCell, int teleportPrice);
};

const int inf = 1e6;

int dp[55][55][55];
vector <int> cellPrice;
int teleportPrice;
int N, M;
bool isTeleport[55][55];

int minCost(int v, int time, int teleportCount) {
	if(v < 0 || v >= N)
		return inf;
	if(cellPrice[v] == inf)
		return inf;
	if(time == 0)
		return (v == 0 && teleportCount == 0) ? 0 : inf;

	int &ret = dp[v][time][teleportCount];

	if(ret > -1)
		return ret;

	ret = inf;

	ret = min(ret, minCost(v-1, time-1, teleportCount) + cellPrice[v]);
	ret = min(ret, minCost(v+1, time-1, teleportCount) + cellPrice[v]);

	if(teleportCount > 0) for(int u = 0; u < N; ++u) {
		if(isTeleport[u][v])
			ret = min(ret, minCost(u, time-1, teleportCount-1) + teleportPrice + teleportCount-1);
	}

	return ret;
}
vector <int> CheapestRoute::routePrice (vector <int> _cellPrice, vector <int> enterCell, vector <int> exitCell, int _teleportPrice) 
{
	cellPrice = _cellPrice;
	teleportPrice = _teleportPrice;
	N = cellPrice.size();
	M = enterCell.size();

	for(__typeof((cellPrice).begin()) it = (cellPrice).begin(); it != (cellPrice).end(); ++it) {
		 if(*it == -1)
			 *it = inf;
	}

	memset(dp, -1, sizeof(dp));
	memset(isTeleport, 0, sizeof(isTeleport));
	for(int i = 0; i < M; ++i) {
		isTeleport[enterCell[i]][exitCell[i]] = true;
	}

	int mnCost = inf;
	int mnMove = inf;

	for(int t = 0; t <= N; ++t) {
		for(int teleportCnt = 0; teleportCnt < M+1; ++teleportCnt) {
			int curCost = minCost(N-1, t, teleportCnt);
			if(curCost < mnCost) {
				mnCost = curCost;
				mnMove = t;
			}
			else if(curCost == mnCost) {
				mnMove = min(mnMove, t);
			}
		}
	}
//	cout << "mnCost = " << mnCost << "\n";
//	cout << "mnMove = " << mnMove << "\n";

	vector <int> ret;
	ret.clear();

	if(mnCost == inf)
		return ret;

	ret.push_back(mnCost);
	ret.push_back(mnMove);
	
	return ret;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <int> p1, vector <int> p2, int p3, bool hasAnswer, vector <int> p4) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p1.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p1[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p2.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p2[i];
	}
	cout << "}" << "," << p3;
	cout << "]" << endl;
	CheapestRoute *obj;
	vector <int> answer;
	obj = new CheapestRoute();
	clock_t startTime = clock();
	answer = obj->routePrice(p0, p1, p2, p3);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << "{";
		for (int i = 0; int(p4.size()) > i; ++i) {
			if (i > 0) {
				cout << ",";
			}
			cout << p4[i];
		}
		cout << "}" << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << "{";
	for (int i = 0; int(answer.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << answer[i];
	}
	cout << "}" << endl;
	if (hasAnswer) {
		if (answer.size() != p4.size()) {
			res = false;
		} else {
			for (int i = 0; int(answer.size()) > i; ++i) {
				if (answer[i] != p4[i]) {
					res = false;
				}
			}
		}
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <int> p0;
	vector <int> p1;
	vector <int> p2;
	int p3;
	vector <int> p4;
	
	{
	// ----- test 0 -----
	int t0[] = {100};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {0};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {0};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 1000;
	int t4[] = {0,0};
			p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
	all_right = KawigiEdit_RunTest(0, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	int t0[] = {0,-1,0,0};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {0};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {2};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 1000;
	int t4[] = {1000,2};
			p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
	all_right = KawigiEdit_RunTest(1, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	int t0[] = {1,2,3};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1.clear() /*{}*/;
	p2.clear() /*{}*/;
	p3 = 100;
	int t4[] = {5,2};
			p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
	all_right = KawigiEdit_RunTest(2, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	int t0[] = {1,0,-1};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {0};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {2};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 0;
	p4.clear() /*{}*/;
	all_right = KawigiEdit_RunTest(3, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	int t0[] = {4,2,1,0,5,6,0,3,0};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {4,4,3,7,5,4,2,5,8,4};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {7,3,5,0,5,4,5,0,8,3};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 8;
	int t4[] = {14,6};
			p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
	all_right = KawigiEdit_RunTest(4, p0, p1, p2, p3, true, p4) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// There is a long corridor which consists of a single horizontal row of n cells, numbered 0 to n-1 from left to right. You are standing in the leftmost cell and you want to move to the rightmost cell. From each cell, you can walk left or right to an adjacent cell. It costs cellPrice[i] to walk into cell i. If the price of a cell is -1, you cannot walk into it.
// 
// Some cells may also contain teleports.  The i-th teleport is located in cell enterCell[i], and when you use that teleport, it will take you to cell exitCell[i].  It costs teleportPrice+x to use a teleport, where x is the number of teleports you have used previously.  When you enter a cell i using a teleport, you do not have to pay cellPrice[i] - you only pay the teleport price. However, if the price of a cell is -1, you cannot enter that cell using a teleport.
// 
// Determine the minimal total cost C required to reach the rightmost cell. Then, determine the minimum number of moves M required to reach the rightmost cell using that minimal cost C. Walking to an adjacent cell counts as a single move, and using a teleport counts as a single move. Return a vector <int> containing exactly two elements. The first element should be C and the second element should be M. If it is impossible to reach the rightmost cell, return an empty vector <int> instead.
// 
// DEFINITION
// Class:CheapestRoute
// Method:routePrice
// Parameters:vector <int>, vector <int>, vector <int>, int
// Returns:vector <int>
// Method signature:vector <int> routePrice(vector <int> cellPrice, vector <int> enterCell, vector <int> exitCell, int teleportPrice)
// 
// 
// CONSTRAINTS
// -cellPrice will contain between 1 and 50 elements, inclusive.
// -enterCell will contain between 0 and 50 elements, inclusive.
// -enterCell and exitCell will contain the same number of elements.
// -Each element of cellPrice will be between -1 and 1000, inclusive.
// -The first element of cellPrice will be between 0 and 1000, inclusive.
// -teleportPrice will be between 0 and 1000, inclusive.
// -Each element of enterCell and exitCell will be between 0 and n-1, inclusive, where n is the number of elements in cellPrice.
// 
// 
// EXAMPLES
// 
// 0)
// {100}
// {0}
// {0}
// 1000
// 
// Returns: {0, 0 }
// 
// Here there is only one cell.
// 
// 1)
// {0,-1,0,0}
// {0}
// {2}
// 1000
// 
// Returns: {1000, 2 }
// 
// First, we use the teleport from cell 0 to cell 2. Then we walk from cell 2 to cell 3. Total cost is 1000+0+0=1000.
// 
// 2)
// {1,2,3}
// {}
// {}
// 100
// 
// Returns: {5, 2 }
// 
// There are no teleports, so we just walk from cell 0 to cell 1 and then to cell 2.
// 
// 3)
// {1,0,-1}
// {0}
// {2}
// 0
// 
// Returns: { }
// 
// The last cell is blocked, so we can't enter there.
// 
// 4)
// {4,2,1,0,5,6,0,3,0}
// {4,4,3,7,5,4,2,5,8,4}
// {7,3,5,0,5,4,5,0,8,3}
// 8
// 
// Returns: {14, 6 }
// 
// 
// 
// END KAWIGIEDIT TESTING

//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!