OJ Board

Code: Select all

ac never mind

Code: Select all

#include <stdio.h>
typedef struct _Node
{
	double dist;
	double price;
} Node;

double dest, rate,cap, invest;
int N;
Node stops[55];
double Ans = -1;
void _bt(int last, int curr, double cost)
{
	int canReachNext = 0;
	int MoreThanHalf = 0;
	int Reachable = 0;
	double StopCost = 0;
	if(curr == N+2)
	{
		if(Ans < 0 || Ans > cost) Ans = cost; return;
	}

	if((stops[curr+1].dist - stops[last].dist) <= cap*rate) canReachNext = 1;
	if((stops[curr].dist - stops[last].dist) <= cap*rate) Reachable= 1;
	if(((stops[curr].dist - stops[last].dist)*2) <= cap*rate) MoreThanHalf = 1;

	if(!Reachable) return;
	if(Ans > 0 && Ans < cost) return;

	StopCost = ((stops[curr].dist - stops[last].dist)*stops[curr].price)/rate;
	StopCost = (int)(StopCost+0.5);
	StopCost += 200;

	if(MoreThanHalf && canReachNext) _bt(last, curr+1, cost);
/*	else if(MoreThanHalf && !canReachNext) _bt(curr, curr+1, cost+StopCost);
	else if(!MoreThanHalf && !canReachNext) _bt(curr, curr+1, cost+StopCost);
	else if(!MoreThanHalf && canReachNext){*/
	else{
		 _bt(last, curr+1, cost);
		 _bt(curr, curr+1, cost+StopCost);
	}
}
int main()
{
	int n, set=0;
	scanf("%lf", &dest);
	/*printf("%lf\n",dest);*/
	while(dest > 0)
	{
		scanf("%lf %lf %lf %d", &cap, &rate, &invest, &N);
		/*printf("%lf %lf %lf %d\n", cap, rate, invest, N);*/
		for(n=1; n<=N; n++)
		{
			scanf("%lf %lf", &stops[n].dist, &stops[n].price);
			/*printf("%lf %lf", stops[n].dist, stops[n].price);*/
		}
		stops[0].dist = 0; stops[0].price = invest;
		stops[n].dist = dest; stops[n].price = 0;

		_bt(0,1,invest*100);
		Ans = (int)(Ans+0.5);
		printf("Data Set #%d\nminimum cost = $%0.2lf\n",++set, Ans/100);
		scanf("%lf", &dest);
		Ans = -1;
	}
	return 0;
}