记录编号	30554	评测结果	AAAAAAAAAA
题目名称	驾车旅行	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2011-10-30 12:44:35	内存使用	19.34 MiB

#include <fstream>
#include <iomanip>
using namespace std;   
  
ifstream input("tour.in");   
ofstream output("tour.out");   
  
int n,head=0,tail=0,pos[1000000]={-1};
double dis,room,power,firstcost,tempdis,tempdis2,minn,inf[50][2],que[1000000][2];
/* As for array inf[][0 or 1] , 0 means the distance to the place which we start the tour , 1 means the cost per L . */
/* As for array que[][0 or 1] , 0 means rest , 1 means cost . */

int main(void)
{   
    int i;   
    input>>dis>>room>>power>>firstcost>>n;
    for (i=0;i<n;i++)
        input>>inf[i][0]>>inf[i][1];   
    que[0][0]=room;   
    que[0][1]=firstcost;
    while (tail<=head/*&&head<=999997*/)   
    {   
        if (pos[tail]>=0)
		{
            tempdis=inf[pos[tail]+1][0]-inf[pos[tail]][0];   
			tempdis2=inf[pos[tail]+2][0]-inf[pos[tail]][0];
		}
		else
		{
            tempdis=inf[0][0];
			tempdis2=inf[1][0];
		}
        if (que[tail][0]*power>=tempdis)
        {
            head++;
            que[head][0]=que[tail][0]-tempdis/power;
            que[head][1]=que[tail][1];
            pos[head]=pos[tail]+1;
            if ((que[tail][0]*power<tempdis2)||(power*(2*que[tail][0]-room)<2*tempdis))
            {   
                head++;   
                que[head][0]=room;   
                que[head][1]=que[tail][1]+(room-que[tail][0]+tempdis/power)*inf[pos[tail]+1][1]+20;   
                pos[head]=pos[tail]+1;   
            }   
        }   
        tail++;   
        if (pos[tail]==n-1)   
            break;   
    }   
    minn=2000000000;   
    for (i=tail;i<=head;i++)   
    {   
        tempdis=dis-inf[pos[i]][0];   
        if (que[i][0]>=tempdis/power)   
            if (que[i][1]<minn)   
                minn=que[i][1];   
    }   
    output<<setiosflags(ios::fixed)<<setprecision(1)<<minn<<endl;   
    input.close();   
    output.close();   
    return(0);   
}