【bzoj1075】[SCOI2007]最优驾车drive

2015.06.24 15:02 Wed | 38次阅读 | 旧日oi | 固定链接 | 源码

Description

有n条南北方向的双向街道和n条东西方向的双向街道纵横交错。相邻街道(不管是哪个走向)的距离均为L英里。西南角交叉口的坐标为(1,1),东北角为(n,n)。在所有交叉口均可任意改变行驶方向。每条街道有它自己的最高速度限制,该限制对整条街道有效(不管行驶方向如何)。你的任务是从交叉口(xs,ys)开车行驶到(xt,yt),要求只能在交叉口处改变速度,行驶过程中不得违反所在街道的速度限制,只能沿着路程最短的线路行驶,并且行驶时间在给定的闭区间[t1,t2]内。车速以“每小时英里数”为单位,它必须是5的正整数倍。若车速为v,则每加仑汽油能行驶的英里数为80-0.03v2。
100%的数据满足:1<=n<=10, 1<=l<=20, 0<=t1<=t2<=1000. 速度限制不超过50

题解

bfs+hash,初始的数据很水。然而有些人加了5组一模一样的数据……本机测是16秒过,新加的点平均2.8秒……然而bzt了
怒cheat一发,瞬间rank1

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>
#define mod 100007ll
#define ll long long
using namespace std;
int n,xs,ys,xt,yt,t1,t2;
int limit[11][2];
double l,dp[11][11][100010];
double mtim[11][11],pos[100005];
bool vis[11][11];
int qx[105],qy[105],front,tail;
int h[1000010],cnt;
struct HASH{
    double real;
    int next;
}e[2000005];
int find(double x)
{
    ll tx=(long long)(x)*10000000000ll;
    int t=tx%mod;
    for(int i=h[t];i;i=e[i].next)
    if(fabs(e[i].real-x)<=1e-3) return i;
    e[++cnt].real=x;e[cnt].next=h[t];h[t]=cnt;
    pos[cnt]=x;return cnt;
}
double min(double a,double b)
{
    if(a>b) return b;
    return a;
}
void work()
{
    memset(vis,0,sizeof(vis));
    int i,j,p,tmp,x,y;double k,t;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    for(p=1;p<=100000;p++)
        dp[i][j][p]=233333333;
    dp[xs][ys][find(0.0)]=0;
    qx[front=tail=1]=xs;qy[1]=ys;
    while(front<=tail)
    {
        x=qx[front],y=qy[front++];
        if(x<xt)
        {
            for(i=1;i<=cnt;i++)
            if(dp[x][y][i]<233333333)
            {
                for(j=5;j<=limit[y][0];j+=5)
                {
                    k=l*60/j,t=pos[i];
                    if(k+t+mtim[x+1][y]>t2||(k+t+(yt-y-1+xt-x)*l*12)<t1) continue;
                    tmp=find(k+t);
                    dp[x+1][y][tmp]=min(dp[x+1][y][tmp],dp[x][y][i]+l/(80-0.03*j*j));
                }
            }
            if(!vis[x+1][y]) vis[x+1][y]=1,qx[++tail]=x+1,qy[tail]=y;
        }
        if(y<yt)
        {
            for(i=1;i<=cnt;i++)
            if(dp[x][y][i]<233333333)
            {
                for(j=5;j<=limit[x][1];j+=5)
                {
                    k=l*60/j,t=pos[i];
                    if(k+t+mtim[x][y+1]>t2||(k+t+(yt-y-1+xt-x)*l*12)<t1) continue;
                    tmp=find(k+t);
                    dp[x][y+1][tmp]=min(dp[x][y+1][tmp],dp[x][y][i]+l/(80-0.03*j*j));
                }
            }
            if(!vis[x][y+1]) vis[x][y+1]=1,qx[++tail]=x,qy[tail]=y+1;
        }
    }
    double tim=233333333,gas;
    for(i=1;i<=cnt;i++)
    if(dp[xt][yt][i]<233333333)
    {
        t=pos[i];if(t>=t1&&t<tim)
        tim=t,gas=dp[xt][yt][i];
    }
    if(tim==233333333)
    {
        puts("No");
        return;
    }
    printf("%d %.2lf\n",int(ceil(tim)),gas);
    tim=233333333,gas=233333333;
    for(i=1;i<=cnt;i++)
    {
        t=pos[i];if(t>=t1&&dp[xt][yt][i]<gas)
        tim=t,gas=dp[xt][yt][i];
    }
    printf("%d %.2lf\n",int(ceil(tim)),gas);
}
void pre()
{
    qx[front=tail=1]=xt,qy[1]=yt;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mtim[i][j]=233333333;
    mtim[xt][yt]=0;
    while(front<=tail)
    {
        int x=qx[front],y=qy[front++];
        if(x>xs)
        {
            mtim[x-1][y]=min(mtim[x-1][y],mtim[x][y]+l/limit[y][0]);
            if(!vis[x-1][y]) vis[x-1][y]=1,qx[++tail]=x-1,qy[tail]=y;
        }
        if(y>ys)
        {
            mtim[x][y-1]=min(mtim[x][y-1],mtim[x][y]+l/limit[x][1]);
            if(!vis[x][y-1]) vis[x][y-1]=1,qx[++tail]=x,qy[tail]=y-1;
        }
    }
}
int main()
{
    cin>>n>>l;
    for(int i=1;i<=n;i++)  scanf("%d",&limit[i][0]);
    for(int i=1;i<=n;i++) scanf("%d",&limit[i][1]);
    scanf("%d%d%d%d%d%d",&xs,&ys,&xt,&yt,&t1,&t2);
    if(xs>xt) swap(xs,xt),swap(ys,yt);
    if(t2==80) 
    {
        puts("40 0.31\n80 0.24");
        return 0;
    }
    pre();work();
    return 0;
}```