旅行规划问题

[c++]代码库

G 先生想独自驾驶汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶e 公里。出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。如何规划才能使旅行的费用最省。

编程任务：

对于给定的d0,c,e,p,和n 以及n个加油站的距离和油价di 和pi，编程计算最小的旅行费用。如果无法到达目的地，输出“No Solution”。

Input
每组测试数据的第1 行是d0,c,e,p,和n。接下来的n 行中每行2个数di 和pi。

Output
输出最小的旅行费用，精确到小数点后2 位。每个答案1行。

Sample Input
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
Sample Output
26.95

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std ;
double f[10005][2];
double ff[10005][2];
bool run()
{
    double d,c,e,p;
    int n,k;
    if ( ! ( cin>>d>>c>>e>>p>>n ) ) return false;
    int i,j;
    ff[0][0]=0;
    ff[0][1]=p;
    for ( i=1; i<=n; i++ )
    {
        cin>>ff[i][0]>>ff[i][1];
    }
    ff[n+1][0]=d;
    ff[n+1][1]=0;
    n++;
    fill ( &f[0][0],&f[10003][1],0 );
    double t,x;
    double y,a[2],b,q;
    for ( i=1; i<=n; i++ )
    {
        for ( j=0; j<i; j++ )
        {
            t=ff[i][0]-ff[j][0];
            x=f[j][0]*e;
            if ( x>=t )
            {
                y= ( double ) t/e;
                a[0]=f[j][0]-y;
                a[1]=f[j][1];
                q=f[j][0];
            }
            else
            {
                y= ( double ) ( ( t-x ) /e );
                if ( y+f[j][0]>c ) continue;
                a[0]=0;
                a[1]=f[j][1]+y*ff[j][1];
                q=f[j][0]+y;
            }
            if ( ff[j][1]<ff[i][1] )
            {
                b= ( d-ff[j][0] ) /e;
                if ( ( c-q ) <b ) b=c-q;
                for ( k=i+1; k<=n; k++ )
                {
                    if ( ( ff[i][0]+b*e ) >=ff[k][0] )
                    {
                        if ( ff[k][1]<ff[j][1] )
                        {
                            b= ( ff[k][0]-ff[i][0] ) /e;
                            break;
                        }
                    }
                    else
                        break;
                }
                a[1]+=b*ff[j][1];
                a[0]+=b;
            }
            if ( a[0]==f[i][0]||f[i][1]==0 )
            {
                if ( a[1]<f[i][1]||f[i][1]==0 )
                {
                    f[i][0]=a[0];
                    f[i][1]=a[1];
                }
            }
            else if ( a[0]>f[i][0] )
            {
                if ( a[1]< ( a[0]-f[i][0] ) *ff[i][1]+f[i][1] )
                {
                    f[i][0]=a[0];
                    f[i][1]=a[1];
                }
            }
            else if ( a[0]<f[i][0] )
            {
                if ( a[1]+ ( f[1][0]-a[0] ) *ff[i][1]<f[i][1] )
                {
                    f[i][0]=a[0];
                    f[i][1]=a[1];
                }
            }
        }
    }
 
    if ( f[n][1]==0 )
    {
        cout<<"No Solution\n";
    }
    else
        printf ( "%.2lf\n",f[n][1] );
    return true;
}
int main()
{
 
    while ( run() );
    return 0;
}

用户注册

用户登录

发表随想

该用户最新代码

编程随想

[c++]代码库

网友评论 (发表评论)

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码