bzoj1075: [SCOI2007]最优驾车drive

这个就是个爆搜+剪枝

1.预处理每个点到终点的最快时间和最慢时间，最快到达都比t2慢，或者最慢到达都比t1快，此时剪枝。

2.Hash判重

3.如果当前时间加上最快到终点时间、当前油量加上到终点所需的最少油量都不如已经搜到的答案优，剪枝。

这样就可以开开心心AC了

const int N = 15;
const DB Eps = 1e-8;
struct State {
	int Ox, Oy;
	State() {}
	State(int _Ox, int _Oy) : Ox(_Ox), Oy(_Oy) {}
	inline State operator -(State &A) { return State(Ox - A.Ox, Oy - A.Oy); }
	inline State operator +(State &A) { return State(Ox + A.Ox, Oy + A.Oy); }
	inline void operator -=(State &A) { *this = *this - A; }
	inline void operator +=(State &A) { *this = *this + A; }
	inline bool operator ==(State &A) { return Ox == A.Ox && Oy == A.Oy; }
	inline bool Check() ;
} St, Ed, Ward[2];
queue<State> Q;
map<LL, bool> Hash[N][N];
bool Vis[N][N];
DB Speed[15];
LL MI[50];
int n;
DB L, Dat[2][N], Size[2]; // 0-> line 1->cow
DB Fast[N][N], Slow[N][N], Cost[N][N];
DB Ans1, MINC, Ans2, MINT;
#define Arr(c, x) c[(x).Ox][(x).Oy]

inline void Input() {
	scanf("%d%lf", &n, &L);
	Rep(i, 2)
		For(j, 1, n) scanf("%lf", &Dat[i][j]);
	scanf("%d%d%d%d", &St.Ox, &St.Oy, &Ed.Ox, &Ed.Oy);
	Rep(i, 2) scanf("%lf", &Size[i]), Size[i] /= 60;
	if(Ed.Ox > St.Ox) Ward[0].Ox = 1;
	else if(St.Ox > Ed.Ox) Ward[0].Ox = -1;
	else Ward[0].Ox = 0;
	if(Ed.Oy > St.Oy) Ward[1].Oy = 1;
	else if(St.Oy > Ed.Oy) Ward[1].Oy = -1;
	else Ward[1].Oy = 0;
	Ward[0].Oy = Ward[1].Ox = 0;
	
	For(i, 1, 14) Speed[i] = 5.0 * i;
	MI[0] = 1;
	For(i, 1, 45) MI[i] = MI[i - 1] << 1;
}

inline bool State::Check() { return Ox >= 1 && Ox <= n && Oy >= 1 && Oy <= n; }
inline void Bfs() {
	For(i, 1, n)
		For(j, 1, n) Fast[i][j] = INF, Slow[i][j] = -INF, Cost[i][j] = INF;
	
	clr(Vis, 0);
	for(Q.push(Ed), Arr(Vis, Ed) = 1, Arr(Fast, Ed) = 0; sz(Q); ) {
		State x = Q.front(), v;
		Q.pop();
		Rep(i, 2) {
			v = x - Ward[i];
			if(v == x) continue;
			if(v.Check()) {
				int MaxSpeed = (int) ((Dat[i][i ? v.Ox : v.Oy] / 5.0) + 0.5) * 5;
				if(MaxSpeed < 5) continue;
				DB Time = L / MaxSpeed;
				if(Arr(Fast, v) > Arr(Fast, x) + Time) {
					Arr(Fast, v) = Arr(Fast, x) + Time;
					if(!Arr(Vis, v)) Arr(Vis, v) = 1, Q.push(v);
				}
			}
		}
	}
	
	clr(Vis, 0);
	for(Q.push(Ed), Arr(Vis, Ed) = 1, Arr(Slow, Ed) = 0, Arr(Cost, Ed) = 0; sz(Q); ) {
		State x = Q.front(), v;
		Q.pop();
		Rep(i, 2) {
			v = x - Ward[i];
			if(v == x) continue;
			if(v.Check() && Dat[i][i ? v.Ox : v.Oy] - 5.0 >= Eps) {
				DB Time = L / 5, _C = L / (80.0 - 0.03 * sqr(5.0));
				Cost[v.Ox][v.Oy] = min(Cost[v.Ox][v.Oy], Cost[x.Ox][x.Oy] + _C);
				if(Arr(Slow, v) < Arr(Slow, x) + Time) {
					Arr(Slow, v) = Arr(Slow, x) + Time;
					if(!Arr(Vis, v)) Arr(Vis, v) = 1, Q.push(v);
				}
			}
		}
	}
}

inline void Dfs(State Now, DB Time, DB C, LL Cnt) {
	bool &H = Arr(Hash, Now)[Cnt];
	if(Time + Arr(Fast, Now) - Size[1] > Eps || Size[0] - Time - Arr(Slow, Now) > Eps ||
	  (Time + Arr(Fast, Now) - Ans1 > Eps && C + Arr(Cost, Now) - Ans2 > Eps) || H) return;
	H = 1;
	
	if(Now == Ed) {
		if(Ans1 - Time > Eps || 
			(abs(Ans1 - Time) <= Eps && MINC - C > Eps)) Ans1 = Time, MINC = C;
		if(Ans2 - C > Eps || 
			(abs(Ans2 - C) <= Eps && MINT - Time > Eps)) Ans2 = C, MINT = Time;
	} else {
		Rep(i, 2) {
			State v = Now + Ward[i];
			if(!v.Check() || v == Now) continue;
			DB Limit = Dat[i][i ? v.Ox : v.Oy];
			For(j, 1, 13)
				if(Limit - Speed[j] > Eps || abs(Limit - Speed[j]) <= Eps) {
					LL _Cnt = Cnt + MI[(j - 1) << 2];
					DB _T = L / Speed[j], _C = L / (80.0 - 0.03 * sqr(Speed[j]));
					Dfs(v, Time + _T, C + _C, _Cnt);
				}
		}
	}
}

inline void Solve() {
	// Get Fast && Slow && Cost
	Bfs();
	
	// Work
	Ans1 = Ans2 = MINC = MINT = INF;
	Dfs(St, 0, 0, 0);
	if(INF - Ans1 > Eps) printf("%d %.2lf\n%d %.2lf\n", 
		(int) ceil(Ans1 * 60 - Eps), MINC, (int) ceil(MINT * 60 - Eps), Ans2);
	else printf("No\n");
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1075");
	#endif
	Input();
	Solve();
	return 0;
}