原題位址
蠻好的一道題目，但是一開始根本想不到這是矩陣快速幂
一開始最簡單的想法就是dp，因為如果兩個相差比較遠的塊中間是不可能走回頭路的，隻有可能是上下移動，是以就能使用dp來維護相鄰兩列之間的轉移
我們用 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示在第 i i i列，第 j j j行，骰子狀态為 k k k的最小代價
這裡的狀态存儲方式需要使用得當一個有 24 24 24種狀态
轉移方程為 f [ i ] [ j ] [ k ] = m i n j j ∈ [ 0 , 3 ] ( f [ i − 1 ] [ j j ] [ c h a n g e ( k ) ] ) f[i][j][k]=min_{jj\in[0,3]}(f[i-1][jj][change(k)]) f[i][j][k]=minjj∈[0,3](f[i−1][jj][change(k)])
但是一看資料範圍 − 1 0 9 ≤ x ≤ 1 0 9 -10^9\leq x \leq 10^9 −109≤x≤109
啥玩意兒？？咕咕咕。。。
我們再傳回去看這個狀态方程… m i n min min???
然後突然靈光一閃
因為隻要是滿足結合律的運算都可以用矩陣快速幂來優化
而 m i n min min必然是滿足結合律的，那麼本題的基本思路就有了
（然而實作起來要有好多細節）
其中一個就是要特判初始方塊和末方塊在同一列的情況
直接spfa吧，因為不一定是直接在同一列上走的
還有一個坑點~~（可能是我程式的問題~~
剛開始讀入了 x 1 , x 2 , y 1 , y 2 x1, x2, y1,y2 x1,x2,y1,y2，結果CE？？
後來改成 x a , x b , y a , y b xa, xb, ya, yb xa,xb,ya,yb後就過了？？（一臉懵逼er
代碼很長（表慌~
//Matrix Is Really a Mysterious Matter, So Enjoy It
#include <cstdio>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f3f3f3f3f
#define X 20
#define MN 10010
const int dd[6][6] = {
{-1, 2, 4, 1, 3, -1}, {3, -1, 0, 5, -1, 2},
{1, 5, -1, -1, 0, 4}, {4, 0, -1, -1, 5, 1},
{2, -1, 5, 0, -1, 3}, {-1, 3, 1, 4, 2, -1}};
typedef long long LL;
int cnt, lst[MN], L[6], in[MN], xa, xb, ya, yb;
LL dis[MN], f[100], g[100][100];
struct Matrix {
int N, M;
LL S[96][96];
inline Matrix(int n = 0, int m = 0, bool sn = 0) : N(n), M(m) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
S[i][j] = INF;
}
}
if (sn) for (int i = 0; i < n; ++i) S[i][i] = 0;
}
friend inline Matrix operator*(const Matrix &a, const Matrix &b) {
Matrix c(a.N, b.M);
for (int i = 0; i < c.N; ++i) {
for (int j = 0 ; j < c.M; ++j) {
for (int k = 0; k < a.M; ++k) {
c.S[i][j] = std :: min(c.S[i][j], a.S[i][k] + b.S[k][j]);
}
}
}
return c;
}
};
struct Node{
int to, nxt;
LL len;
}e[MN << 1];
inline void add(int u, int v, int w) {
e[++cnt].to = v;
e[cnt].nxt = lst[u];
e[cnt].len = w;
lst[u] = cnt;
}
inline int getsta(int x, int y, int top, int front) {
int now = -1;
for (int i = 0; i < 6; ++i) {
if (i != top && i != 5 - top) ++now;
if (i == front) return x * 96 + y * 24 + top * 4 + now;
}
return -1;
}
inline void init() {
for (int x = 0; x < X; ++x) {
for (int y = 0; y < 4; ++y) {
for (int top = 0; top < 6; ++top) {
for (int front = 0; front < 6; ++front) {
if (front == top || front == 5 - top) continue;
int left = dd[top][front], u = getsta(x, y, top, front);
int tt, v;
if (x) {
tt = 5 - left;
v = getsta(x - 1, y, tt, front);
add(u, v, L[tt]);
}
if (x + 1 < X) {
tt = left;
v = getsta(x + 1, y, tt, front);
add(u, v, L[tt]);
}
if (y) {
tt = 5 - front;
v = getsta(x, y - 1, tt, top);
add(u, v, L[tt]);
}
if (y < 3) {
tt = front;
v = getsta(x, y + 1, tt, 5 - top);
add(u, v, L[tt]);
}
}
}
}
}
}
inline void spfa(int sr) {
std :: queue <int> team;
for (int i = 0; i < X * 96; ++i) dis[i] = INF;
dis[sr] = 0;
in[sr] = 1;
team.push(sr);
while (!team.empty()) {
int now = team.front();
team.pop();
for (int i = lst[now]; i; i = e[i].nxt) {
if (dis[e[i].to] <= dis[now] + e[i].len) continue;
dis[e[i].to] = dis[now] + e[i].len;
if (!in[e[i].to]) team.push(e[i].to), in[e[i].to] = 1;
}
in[now] = 0;
}
}
inline void rec(int x, LL A[]) {
for (int y = 0; y < 4; ++y) {
for (int top = 0; top < 6; ++top) {
for (int front = 0; front < 6; ++front) {
if (front == top || front == 5 - top) continue;
int id = getsta(x, y, top, front);
A[id % 96] = dis[id];
}
}
}
}
inline Matrix ksm(Matrix a, int b) {
Matrix ret(96, 96, 1);
for (; b; b >>= 1, a = a * a) if (b & 1) ret = ret * a;
return ret;
}
inline void doit() {
int dif = std :: abs(xa - xb), x = X >> 1;
LL ans = INF;
spfa(getsta(x, ya, 0, 1));
if (!dif) {
for (int top = 0; top < 6; ++top) {
for (int front = 0; front < 6; ++front) {
if (front == top || front == 5 - top) continue;
ans = std :: min(ans, dis[getsta(x, yb, top, front)]);
}
}
printf("%lld\n", ans);
return;
}
rec(x, f);
for (int y = 0; y < 4; ++y) {
for (int top = 0; top < 6; ++top) {
for (int front = 0; front < 6; ++front) {
if (front == top || front == 5 - top) continue;
int sr = getsta(x, y, top, front);
spfa(sr);
rec(x + 1, g[sr % 96]);
}
}
}
Matrix A(96, 96);
for (int i = 0; i < 96; ++i) {
for (int j = 0; j < 96; ++j) {
A.S[i][j] = g[i][j];
}
}
A = ksm(A, dif);
for (int i = 0; i < 96; ++i) {
for (int j = 0; j < 96; ++j) {
if (j / 24 == yb) ans = std :: min(ans, f[i] + A.S[i][j]);
}
}
printf("%lld\n", ans);
return;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
for (int i = 0; i < 6; ++i)
scanf("%d", &L[i]);
scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
--ya;
--yb;
if (xa > xb) std :: swap(L[2], L[3]);
init();
doit();
}
return 0;
}
//The Elder, The Myths of Time
//U{uJUjujuJjY[>vJjJjYv>[{jYuJuJJ<<[JJjY[<v[Y{ujJYu{vi>>v>vv[v[?[LjYJ{vi^>Y[<^>{JYJYj{JLJYuJJ{JYJ{YJu[
//J>[{v[v{?[><vUL<<?riYJ<^>[>v><<uj>r><^<uvi^?>v>v</>2j<r[LYLJ><r><?>^^qPviiuqUrr><>>v?[>v>[>[?v>??v>>
//jLjJjYjYJL>/M&&/<iiN&&&vi<{L[i[&&Y/i/>&&&q^^[L{</u&&&&&GZZGqM&&u??i>&@&L>?&&@vJYujj[J{Y{Y{J{JYJLJLYv
//{LYJ{jYJ[>M&@&&B&X&&@F&&M2L<u&B&&M&MP&&XZ&&qYL^>Z&&Y>&&j/^r<5&@2/<F&&&PEP&@&[email protected]{[{[{[YLL
//Jvj{YLY{{^&@8&O&&&[email protected]@P/5&&M&Z&&BGqu1NB&B>E&&&&//Xkj&&@jSkNiY&&&&G''1&&<:/i::/>?{[{v{L{v{[{[{[Y>
//{L{JYjLYvr&&@&MEGSuSkNFSFuiiU&&&&EZNuF5PkS5S^iu5j&&E51Yu&&@UJ2FEJS>B&Z,O&&[email protected]&G^[v{v{v{vL[{[L[Yvv
//J?JLYL{L{r?^Z&@G0&&O^[email protected]&O/r<<v&&EO0&&[//X&&r::'<&&>:iX&&@&&M>^<r:_M&&&&&&O./:_&&&^?LvLvLvLv[v{vLv[>
//{vLYLL[L>1EN&&@&&&&@vYJ&&M/vNNG&&M&&&&v<<E&&5SqqG&&EN&&[email protected]&Mq&&O2^/'@&&>_&&&XEEF&&&/?[[v[v[vLv[vLvLv?
//{>L[{[Lv?Yk2J<^^YB&MXPN&&0r<22Ji:_^1&&&@&@&@[email protected]@&&&&@8P&@&XZM&&MPjM&U''qBGJ12uZMPr>[?v?v>L?[?vvLvL>
//[>[[?[[Lv?r<^<r</i/i/i/i/^<>/:"i[kXE080EPSFqZ00EqPSXFPFqPPXkSXq0qZOONSS2/_,:/i//:i<>>?>v>v>?>v>?>v>>
//L<[>[>[>v>?>>>><><><><>r><<//[email protected]</i<<><>>><><><>>?>>>v>vr
//v>?[>?>v>v>?>v>><><>>>>><[email protected]>[Ju{{[v>JjjjS00uJ1S10GO5r:ir<<><><><><><><>>?<<
//vrv>>>>>><>>?>><><><><></:[email protected]?L<r//::_":::/_"_//i/<[L{FSk12UGOS</i<<><><><>r><>r<<>^
//<<>><><><><><><><><>r<i:/O&BGZNX11U5Y{L[<r^><^/i//::::_"__,___,_,",,:<<[email protected]@<:i<r>r<r<r<^<r<r<<<
//vi><><<<>r<r<<><><>r<i"[email protected]&MO8NNFUL[v{>??[i<v[i/^i:/:/:/::_:::_:":_:__,::<[email protected]:i<r<^<^<^<^<r<r<^
//<r<<^<r<r<r<^<<<r<r<i_v&&MOOZZX5JL?jj{[>vv>[>i<>/::/_","_:"_.,,"_:_:_:"::^>[email protected]//iririr^r^<^<rrri
//</<^<^<^<^r^r^r^<^r/:/&&B8O8OEN12[YU1jjL><>r?i>^i/i//_"_:,,' ''',,,,",:"::<>U5PNO&X_i/^i^/ri^i^i^ir/
//^/^<iririri^iriii^ii,X&MOO8OZZPSJ[uS2UYJ></ii<//:://:/":_:_",",,',,,',_/:::<[F08O&0_:i/i/i/i/ii^i^//
//<:ri^i^i^/i/iii/i//:_M&MOOO8Z0quuuS51uJ>?<^///i::__,:_:::::::__,_,,',_::/"/<Yjq8M&u'//i/i///i///^ii:
//^:ii/iii/i/i/i///i//.O&BOMOOG8F5SF51j2jvr>>>^/:/,.'',__,,/:"'' ''''_'_":::/>J1qOM&i,://i/i///i//
//^:i///i/i:/:_:&&BOMOO0XFF221EEEXkS52FFk22{^'"i: ,:/://i/i/::^i/"_,/>>2OM&M._/:/:/:/:/:i:
///::/:/:/:///:/::"'/MBBOMOMOGkS0ONS5UJ[ri:>{Sji .P0uJUL[<</i<Y1FJi'/vPM&@['::::/:/:/:::/://:
///_/:/:/:/:/:::/::::":',qZ0OOOE8MqN&EFS0q0qqNGPkF5i :&BPk&MNjju1jY><i_',_/8M{[email protected]&@J __:"::::::/::::::_
///":::/:/::::":::":_:_':GF1SXSFU2u&SjEMF5FkU5kL<jZOJL&&&&@'>5k0ZMM0Pq5/'^Pj&&YEOS'',:":":":::::::"::_
//:,:::":::":":""_:_:""'_0quU2X1FuuMU<j[L<<<>i//i./[email protected]@i "&>'/L<:,' ''/5OMu'OE.'j[''__"_:_:_"_:_:_:_:,
//:,::":":":_:_:______,,'2E1US1F55JXPY{r^<///><</:r8&@>. ?&2./Lvv></:.<k, _Mv''?/'___,_,_,_,",","_"_,
//:':_:_"____,_,",_,_,_.',E5XU51F25uP2UJJ></:__,/jBBNY/,' /&F::/:/",'' :__Fu"/:i',,,,_,_,_,_,_,_,_,_'
//_'_"__,_,_,,,_,,,_,_,_' JG55251S1FU5uuu2u5uuJ5G8jYUU/_' ' '15522ju[>r>YL>v"/:i''',',,,,,',',.,.,,_,'
//_'_,,._,,,,.,,,.,',','' :0Su52F5FSS1jri:_,_'i5N5NM&BZF2>kMS:/?JuuLv>?r:'_/^,:"''.'.'.',',',.,',.,','
//,'.,.,',.,.,',',','.'.'' SZP252S5SFXkqU{?[?[LuuFXNqGEPJi^><^' _/<//:/:ii^/"_,','.'''.'''.'''.',',''
//_ ,'..,','.','''.'.'.''' ,SX1F2FUFFXk2FkujJY>r/:"".' '' .,_,/<UuY<>^iii,,''''''''''''''''''''''
//'''.''''''''''''''''''''' j0S1S5F5SU[/jqkkX2j><^^/,'''' ''.,//r^<^ri:_:/</, '''''''''''''''''''''''
//, .''''''''''''''''''''''' ^O5FSk5F51Yi,LZMOOOMMMOOZOZPqqPPS2>v{?//,""":^<' ''''' '''''''''''''''''
//' '''''''''''''''''''''''' kX2SSS1S5SL//uF2uFuUjYLJ?[Yv<[<i_''///::://^[" ' ''''''' ' ''''''' ' ''
//' ''' ''''''''''''' ' ' >X1UFFS5PkSJ>:[JLLY[L^^r>/i/:.'',,"_//rir^LJ/ ' ' ' ' ' ' ' ' ' ' '
//' '''' ''' ' ' ' ' ' /&0YSUkSkkqq05<:YuL<>>>r<r^//::":_:_,"r<??uY, ' '
//' ' ' ' ' 'N&&B{vXkSXqXNq8S[iL[>/:,:_,_, '''._',:<>?vL:
// u&&@[email protected]@jiuP0PqPq0G0Puujjv</i:i/:,"_::/<uuuL<'
//' 'vFM&&&&BMOMOB&8i:L0EGN00GZG0NPNFUJuUFUujUjujjLY[:
// :jM&&&&&&&@[email protected]&5_'rjXZ8E8N0P0qZZGGOOO00SF2Ujj[/LEu{>^_
// 'LZ&&&@@MBMMOMOMOO8OOMOMM&@U,',i>US00ZXkFXSX21ujJjJUuJr' Z&&&&&&@&OS>_
// ':vuZ&&&&[email protected]&&>,,:_:/vuq0NSk2Y<ri^ir/, Z&[email protected]&&@&@8U^
//PZ&&&@&@[email protected]&k/_/"_ .:>i"_"' @[email protected]&&&@O2Y/
//&@MMOO8OZGEG0ZE8ZGEGZ88MO8GOGO8MOO8O8MM&8: '' _[XuX2jj/ '&[email protected]&&&@&Zu/'
//[email protected]" i8GOSj5LS150&0 '&M8N0NE0ENZEZEZEZEZEZ08GOM&&&&&ZJ'
//[email protected]@j J&&&&MGXuj<uUB&&0 ZBZENZqZ0ZEZ0E0GEZ0Z0Z0Z0ZEGZOM&&&
//808E8EGEGZGZ80GEZEGEZZOOM8OZO8O8OZOGO8OG8GM&G [email protected][>8q/u8Z: [email protected]
//ZZE8ZGE8Z8ZGZG0GE8GGEZOMO8ZOZOZ8Z8Z8Z8ZZ0GEO&M Jv'/jGMMP1Z 'iLBGZ0ZN0NE0EEZ0ZEZ0EqZ0ZEZ0ENZNE00
//808Z8ZGE8E8ZGG8GGE8E8EMMME8ZGEZEGE8Z8EZ08EZZO&& Y2''NGO8<Xi "Y2M0GEZEE0ENZNE0ZNENZEG0Z0E0E0ENZq
//[email protected]@&/ vEXMGNq5FO' 15OG080GEZEZNE0ENE0EEGEZ0ENZNE0EN0
//8NGZ8EGZ8EGZOOFYk8&&&&[email protected]&&&@&&&&&&&@&@&&&/.M&@&BM<>PM^ 'uUMEZEG0ZEZ0Z0E0ZEZEZEG0ENZNE0E0Eq
//88EGE8E8E8ZO&&Y:'''''/LOGOGGZM&L ''' ' 2&OM/''EOX5{u&k S{LOO08Z8ZZEGE8Z88OG8Z8ZZ0ZNZ0ZNE00
//MZOZZ0GZGZM8i/>LLv>,i'/B&&&MGM&M88MOB& @[email protected]@ M&Eu8MLNZk&G[OO8O&&&G8ZM&&&&&&&&@OEE0E0Z0ZNEq
//[email protected]&uU1kN/ F&@&X /MM25SXSqGM >&GqkPSXUXM& <.''_>OPuNi::8BMG":[email protected]@&S/...://_kONE0Z0ENEE0
//8OBOOE8EM/ :r/,LP FF rZ&M_ ''''r ','''''i&@' <v' JBY @M&P &&E 10/ X8ZZ0Z0ENZ0GN
//008BMMGGONXM&? YE >&&@&[email protected]@&&&&&& G&&&@&&&M& &&O&P MJ ,&B&M &&G .&&X _&OZ0E0E0Z0000
//MEZOBOOGM&&@_ S&5 E> <M&&&B&&&&&> <O Z&&@&u[S&& B&B8: 'Mu '&&&S @&&< /^,>G&@OEZ0EEZEZNEN
//MMGOMMOMM{ [email protected]&&u N&O/ '1&@Bu' q&E [BN8k && ,_ /OqL' " &&B Y>LYu28MOZ8ZGE0EE00
//[email protected]/j&@X ' 8&&@&0>:qB< LO&&&Mi ' :[email protected][u^X8F[q&&J:[FB05kM&Y 2ZXPN XMZEZ0Z0Z0Zq
//E0EOOMOOO&&&[email protected]&&[email protected]@&OOOB&&@&OGZM&&&&&&&&@by t123yh&&X^[email protected]&N&[email protected]&[email protected]? /L{vi [MOqEq0N0N0qN
![MCDM方法及matlab應用五：ＭＡＢＡＣ方法及matlab應用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)