记录编号	371457	评测结果	WWAAAWWWWA
题目名称	1472.[CEPC 2003] 骰子游戏	最终得分	40
用户昵称	KZNS	是否通过	未通过
代码语言	C++	运行时间	1.465 s
提交时间	2017-02-16 10:10:40	内存使用	0.45 MiB

//KZNS
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int, int> pr;
#define tps 96
const LL Tmax = (LL)(1e12);
int L[7] = {0};
int x1, x2, y1, y2;
void rin() {
	for (int i = 1; i <= 6; i++)
		scanf("%d", L+i);
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
}
int cg[7][4][4][2];//i???,???j?????,???????????0,??1
int cm[7][4];//??????
int rcm[7][7] = {0};//cm?????
namespace fir {//?????
	void turna(int *tp) {//???????
		int u;
		u = tp[0];
		tp[0] = tp[2];
		tp[2] = 7-u;
	}
	void turnw(int *tp) {//???????
		int u;
		u = tp[1];
		tp[1] = tp[0];
		tp[0] = 7-u;
	}
	void turnq(int *tp) {//???????
		int u;
		u = tp[1];
		tp[1] = tp[2];
		tp[2] = 7-u;
	}
	void mkcg() {
		int tp[3];//?????
		//0????,1????,2????
		//?????????,????????7
		if (x1 <= x2) {
			//????????????,?????????????
			tp[0] = 1;
			tp[1] = 2;
			tp[2] = 3;
			x2 -= x1;
			x1 = 0;
		}
		else {
			//?????????,?????????????
			tp[0] = 1;
			tp[1] = 2;
			tp[2] = 4;
			x2 = x1-x2;
			x1 = 0;
		}
		y1--;
		y2--;
		//???????????
		int u = 0;
		for (int i = 1; i <= 6; i++) {
			u = 0;
			for (int j = 1; j <= 6; j++)
				if (!(j == i || j == 7-i))
					cm[i][u++] = j;
			sort(cm[i], cm[i]+4);
			for (int j = 0; j < 4; j++)
				rcm[i][cm[i][j]] = j;
		}
		for (int i = 1; i <= 6; i++) {
			while (tp[0] != i) {//????,??i????
				turna(tp);
				if (tp[0] == i)
					break;
				turnw(tp);
			}
			for (int j = 0; j < 4; j++) {//????????????
				while (tp[1] != cm[i][j])
					turnq(tp);
				//????????????
				cg[i][j][0][0] = tp[1];
				cg[i][j][0][1] = rcm[tp[1]][7-tp[0]];
				
				cg[i][j][1][0] = tp[2];
				cg[i][j][1][1] = rcm[tp[2]][tp[1]];
				
				cg[i][j][2][0] = 7-tp[1];
				cg[i][j][2][1] = rcm[7-tp[2]][tp[0]];
				
				cg[i][j][3][0] = 7-tp[2];
				cg[i][j][3][1] = rcm[7-tp[2]][tp[1]];
			}
		}
	}
}
class cp {
public:
	bool operator () (const pr a, const pr b) {
		return b < a;
	}
};
class poi {
public:
	LL M[tps][tps];
	void a0() {
		memset(M, 0, sizeof(M));
	}
	void b0() {
		memset(M, 0, sizeof(M));
		for (int i = 0; i < tps; i++)
			M[i][i] = 1;
	}
	void c0() {
		for (int i = 0; i < tps; i++)
			for (int j = 0; j < tps; j++)
				M[i][j] = Tmax;
	}
}Zr;
poi operator * (const poi &a, const poi &b) {
	poi ans;
	ans = Zr;
	for (int i = 0; i < tps; i++)
		for (int j = 0; j < tps; j++)
			for (int k = 0; k < tps; k++)
				ans.M[i][j] = min(ans.M[i][j], a.M[i][k]+b.M[k][j]);
	return ans;
}
poi A;
namespace mkM {
	inline int tid(int *tp) {
		return tp[2]+(tp[1]-1)*4+tp[0]*24;
	}
	inline void rid(int a, int *tp) {
		tp[2] = a%4;
		a /= 4;
		tp[1] = a%6+1;
		a /= 6;
		tp[0] = a;
	}
	inline int ttid(int *tp) {
		return tp[3]+(tp[2]-1)*4+tp[1]*24+tp[0]*96;
	}
	inline void rrid(int a, int *tp) {
		tp[3] = a%4;
		a /= 4;
		tp[2] = a%6+1;
		a /= 6;
		tp[1] = a%4;
		a /= 4;
		tp[0] = a;
	}
	const int mpsz = 20;
	bool mpud[2000], ud[100] = {0};
	queue<int> ls;
	priority_queue<pr, vector<pr>, cp> llss;
	void kz(int a) {
		int tp[4];
		int x, y, t, f;
		pr u;
		rid(a, tp+1);
		tp[0] = 10;
		memset(mpud, 0, sizeof(mpud));
		llss.push(make_pair(0, ttid(tp)));
		while (!llss.empty()) {
			u = llss.top();
			llss.pop();
			if (mpud[u.second])
				continue;
			else
				mpud[u.second] = true;
			rrid(u.second, tp);
			x = tp[0];
			y = tp[1];
			t = tp[2];
			f = tp[3];
			if (x == 11) {
				A.M[a][tid(tp+1)] = u.first;
				ls.push(tid(tp+1));
			}
			if (y > 0) {
				tp[0] = x;
				tp[1] = y-1;
				tp[2] = cg[t][f][0][0];
				tp[3] = cg[t][f][0][1];
				llss.push(make_pair(u.first + L[tp[2]], ttid(tp)));
			}
			if (x < mpsz) {
				tp[0] = x+1;
				tp[1] = y;
				tp[2] = cg[t][f][1][0];
				tp[3] = cg[t][f][1][1];
				llss.push(make_pair(u.first + L[tp[2]], ttid(tp)));
			}
			if (y < 3) {
				tp[0] = x;
				tp[1] = y+1;
				tp[2] = cg[t][f][2][0];
				tp[3] = cg[t][f][2][1];
				llss.push(make_pair(u.first + L[tp[2]], ttid(tp)));
			}
			if (x > 1) {
				tp[0] = x-1;
				tp[1] = y;
				tp[2] = cg[t][f][3][0];
				tp[3] = cg[t][f][3][1];
				llss.push(make_pair(u.first + L[tp[2]], ttid(tp)));
			}
			
		}
	}
	void mk() {
		int tp[3] = {y1, 1, 0};
		ls.push(tid(tp));
		int u;
		while (!ls.empty()) {
			u = ls.front();
			ls.pop();
			if (ud[u])
				continue;
			else
				ud[u] = true;
			kz(u);
		}
	}
}
void fff() {
	Zr.c0();
	A = Zr;
}
poi fpw(int s, poi a, int b) {
	poi ans;
	b--;
	for (int j = 0; j < tps; j++)
        ans.M[s][j] = a.M[s][j];
	while (b) {
		if (b&1) {
			ans = ans * a;
		}
		b >>= 1;
		a = a*a;
	}
	return ans;
}
void pf() {
    int tp[3];
	int s, a, b;
	tp[0] = y1;
	tp[1] = 1;
	tp[2] = 0;
	s = mkM::tid(tp);
	tp[0] = y2;
	tp[1] = 1;
	tp[2] = 0;
	a = mkM::tid(tp);
	tp[0] = y2;
	tp[1] = 6;
	tp[2] = 3;
	b = mkM::tid(tp);
	A = fpw(s, A, x2);
	LL ans = Tmax;
	for (int i = a; i <= b; i++)
		ans = min(ans, A.M[s][i]);
	printf("%lld\n", ans);
}
int main() {
	freopen("dicecontest.in", "r", stdin);
	freopen("dicecontest.out", "w", stdout);
	rin();
	fir::mkcg();
	fff();
	mkM::mk();
	pf();
	return 0;
}
//UBWH