记录编号	371518	评测结果	AAAAAAAAWW
题目名称	[CEPC 2003] 骰子游戏	最终得分	80
用户昵称	KZNS	是否通过	未通过
代码语言	C++	运行时间	1.402 s
提交时间	2017-02-16 11:22:05	内存使用	0.34 MiB

//KZNS
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
#define TPS 96
#define INF 1000000000000ll
class matrix {
    public:
        LL M[96][96];
    void i0() {
        memset(M, 0, sizeof(M));
    }
    void mx() {
        for (int i = 0; i < TPS; i++)
            for (int j = 0; j < TPS; j++)
                M[i][j] = INF;
    }
};
matrix operator * (matrix a, matrix b) {
    matrix c;
    c.i0();
    for (int i = 0; i < TPS; i++) {
        for (int j = 0; j < TPS; j++) {
            c.M[i][j] = INF;
            for (int k = 0; k < TPS; k++)
                c.M[i][j] = min(c.M[i][j], a.M[i][k] + b.M[k][j]);
        }
    }
    return c;
}
matrix fpw(int s, matrix a, int b) {
    matrix c;
    c.mx();
    for (int i = 0; i < TPS; i++)
        c.M[s][i] = a.M[s][i];
    b--;
    while (b) {
        if (b & 1)
            c = c * a;
        a = a * a;
        b >>= 1;
    }
    return c;
}
int V[6];//相比较于正常骰子，这里所有面的点数-1，则相对面的点数和为5 
int X0, Y0, X1, Y1, X;
int wls[6][4];//骰子上面为i时，相邻面第j大的点数 
int rls[6][6];
int cg[6][4][4][2];//上面为i，正面为第j大的相邻面时，向上右下左滚动后的上正面点数 
int dice[3] = {0, 1};//WSA骰子的上正左面 
matrix A;
namespace fir {
    void iDice() {//初始化骰子 
        if (X0 <= X1)
            dice[2] = 2;
        else
            dice[2] = 3;
        X = abs(X0 - X1);
        Y0--;
        Y1--;
    }
    void tA() {//向左滚 
        int u;
        u = 5 - dice[2];
        dice[2] = dice[0];
        dice[0] = u;
    }
    void tW() {//向上滚 
        int u;
        u = 5 - dice[0];
        dice[0] = dice[1];
        dice[1] = u;
    }
    void tQ() {//俯视，逆时针旋转骰子 
        int u;
        u = 5 - dice[1];
        dice[1] = dice[2];
        dice[2] = u;
    }
    void iCg() {
        int u; 
        for (int i = 0; i < 6; i++) {
            u = 0;
            for (int j = 0; j < 6; j++) {
                if (i == j || 5 - i == j)
                    continue;
                rls[i][j] = u;
                wls[i][u++] = j;
            }
        }
        for (int i = 0; i < 6; i++) {
            while (true) {
                tA();
                if (dice[0] == i)
                    break;
                tW();
                if (dice[0] == i)
                    break;
            }
            for (int j = 0; j < 4; j++) {
                while (dice[1] != wls[i][j])
                    tQ();
                cg[i][j][0][0] = dice[1];
				cg[i][j][0][1] = rls[dice[1]][5-dice[0]];
				
				cg[i][j][1][0] = dice[2];
				cg[i][j][1][1] = rls[dice[2]][dice[1]];
				
				cg[i][j][2][0] = 5-dice[1];
				cg[i][j][2][1] = rls[5-dice[2]][dice[0]];
				
				cg[i][j][3][0] = 5-dice[2];
				cg[i][j][3][1] = rls[5-dice[2]][dice[1]];
            }
        }
    }
    void init() {
        iDice();
        iCg();
    }
}
namespace mkA {
    class poi {
        public:
            int cost, x, y, w, s;
    };
    bool operator < (poi a, poi b) {
        return a.cost > b.cost;
    }
    inline int zip(int a, int b, int c) {
        return a*24 + b*4 + c;
    }
    int mv[4][2] = {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0}
    };
    bool ud[14][4][6][4];
    void kz(int y, int w, int s) {
        memset(ud, 0, sizeof(ud));
        priority_queue<poi> ls;
        int nu = TPS;
        int id = zip(y, w, s);
        ls.push((poi){0, 7, y, w, s});
        poi u;
        int x, cost;
        int xx, yy;
        while (!ls.empty() && nu) {
            u = ls.top();
            ls.pop();
            cost = u.cost;
            x = u.x;
            y = u.y;
            w = u.w;
            s = u.s;
            if (ud[x][y][w][s])
                continue;
            else {
                ud[x][y][w][s] = true;
                if (x == 8) {
                    A.M[id][zip(y, w, s)] = u.cost;
                    nu--;
                }
            }
            for (int i = 0; i < 4; i++) {
                xx = x + mv[i][0];
                yy = y + mv[i][1];
                if (0 <= xx && xx < 14 && 0 <= yy && yy < 4) {
                    u.cost = cost + V[cg[w][s][i][0]];
                    u.x = xx;
                    u.y = yy;
                    u.w = cg[w][s][i][0];
                    u.s = cg[w][s][i][1];
                    ls.push(u);
                }
            }
        }
    }
    void make() {
        A.mx();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 6; j++) {
                for (int k = 0; k < 4; k++) {
                    kz(i, j, k);
                }
            }
        }
    }
}
void init() {
    for (int i = 0; i < 6; i++)
        scanf("%d", &V[i]);
    scanf("%d %d %d %d", &X0, &Y0, &X1, &Y1);
    fir::init();
}
void ansit() {
    matrix C;
    int s, a, b;
    s = mkA::zip(Y0, 0, 0);
    a = mkA::zip(Y1, 0, 0);
    b = mkA::zip(Y1, 5, 3);
    C = fpw(s, A, X);
    LL ans = INF;
    for (int i = a; i <= b; i++)
        ans = min(ans, C.M[s][i]);
    printf("%lld\n", ans);
}
int main() {
    freopen("dicecontest.in", "r", stdin);
    freopen("dicecontest.out", "w", stdout);
    init();
    mkA::make();
    ansit();
    return 0;
}
//UBWH