| 记录编号 |
85440 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[CEPC 2003] 骰子游戏 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.973 s |
| 提交时间 |
2014-01-04 11:09:02 |
内存使用 |
0.35 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
typedef long long ll;
const ll INF=1e17;
const int SIZEN=145,SIZEH=4,NUMSIDE=6;//行数/哪一面朝上,共24种状态
const int SIZECIR=20;//这里定为:最多迂回10格,即"尝试区"大小(0~SIZECIR-1)
int N;//有意义的状态数
int delta;//即x2-x1,相差列数
pair<int,pair<int,int> > state[SIZEN+1];//每个状态是在哪一行,哪一面朝上,哪一面朝前
int statelis[SIZEH+1][NUMSIDE+1][NUMSIDE+1]={0};//哪一行,哪一面朝上,哪一面朝前对应的状态编号
int S;//起点
vector<int> T;//终点集对应的状态们
int sticker[NUMSIDE+1]={0};//骰子每一面上的数
int opposite[NUMSIDE+1]={0};//每个面都和哪个面相对
int onleft[NUMSIDE+1][NUMSIDE+1]={0};//当i在上面j在前面时,左侧的面
vector<pair<int,int> > c[SIZEN*SIZECIR+1];//在"尝试区"内的邻接表
int TA_NUMS;//"尝试区"内的状态总数
void printstate(int x){//调试接口,输出状态x的具体含义
//格式为:x,y,up,front
int temp=x%N;
cout<<"(";
cout<<(x-1)/N<<",";
cout<<state[temp].first<<","<<state[temp].second.first<<","<<state[temp].second.second<<")";
}
void printgraph(void){//调试接口,输出图
for(int i=1;i<=TA_NUMS;i++){
printstate(i);
cout<<" lis:";
for(int j=0;j<c[i].size();j++){
cout<<"**";
printstate(c[i][j].first);
cout<<" "<<c[i][j].second<<".. ";
}
cout<<endl;
}
}
void printarray(ll *s,ll n){//调试接口,从地址s开始连续输出n个元素
for(int i=0;i<n;i++){
if(s[i]!=INF) cout<<s[i]<<" ";
else cout<<-1<<" ";
}
cout<<endl;
}
void printarray(int *s,int n){//调试接口,从地址s开始连续输出n个元素
for(int i=0;i<n;i++){
if(s[i]!=INF) cout<<s[i]<<" ";
else cout<<-1<<" ";
}
cout<<endl;
}
class MATRIX{
public:
int n,m;//n行m列
ll s[SIZEN+1][SIZEN+1];
MATRIX(){//初始化为零
m=n=0;
for(int i=0;i<SIZEN;i++) for(int j=0;j<SIZEN;j++) s[i][j]=INF;
for(int i=0;i<SIZEN;i++) s[i][i]=0;
//初始化为无边的矩阵(权值均为inf)
}
void print(void){//调试接口,输出矩阵(若为inf则相应项输出0)
cout<<"size:"<<n<<" "<<m<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]<=INF) cout<<s[i][j]<<" ";
else cout<<-1<<" ";
}
cout<<endl;
}
}
void printele(void){//调试接口,输出整个矩阵,其中对s[i][j]输出:i状态的意义,j状态的意义,(i,j)的值
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printstate(i);cout<<"->";printstate(j);
cout<<s[i][j]<<endl;
}
}
}
void assign_one(int sn){//赋值为sn行的无边矩阵
n=m=sn;
for(int i=1;i<=n;i++) s[i][i]=0;
}
};
MATRIX operator * (MATRIX a,MATRIX b){//矩阵乘法,结果对MOD取模
MATRIX c;
c.n=a.n;c.m=b.m;
int i,j,k;
for(i=1;i<=c.n;i++){
for(j=1;j<=c.m;j++){
c.s[i][j]=INF;
for(k=1;k<=a.m;k++){
if(a.s[i][k]==INF||b.s[k][j]==INF) continue;
c.s[i][j]=min(c.s[i][j],a.s[i][k]+b.s[k][j]);
}
}
}
return c;
}
MATRIX quickpow(MATRIX a,ll n){//a^n,a的长宽相等
MATRIX ans;ans.assign_one(a.n);
while(n){
if(n&1) ans=ans*a;
a=a*a;
n>>=1;
}
return ans;
}
void SPFA(vector<pair<int,int> > c[],int s,int n,ll f[]){//SPFA
//图的信息在邻接表c中,以s为起点,节点1~n,最短路信息储存在f中
queue<int> Q;
bool *inq=new bool[n+1];
int i,u,v,w;
for(i=1;i<=n;i++) f[i]=INF,inq[i]=false;
inq[s]=true,f[s]=0,Q.push(s);
while(!Q.empty()){
u=Q.front(),Q.pop();
inq[u]=false;
for(i=0;i<c[u].size();i++){
v=c[u][i].first,w=c[u][i].second;
if(f[v]>f[u]+w){
f[v]=f[u]+w;
if(!inq[v]) inq[v]=true,Q.push(v);
}
}
}
}
void makegraph(MATRIX &I,MATRIX &G){//得到起点到第一行的最短路矩阵I和这一行到下一行的最短路矩阵G
ll f[SIZEN*SIZECIR+1]={0};
int i,j;
I.n=1,I.m=N;
int TN=SIZECIR/2-1;
SPFA(c,S+TN*N,TA_NUMS,f);
for(i=1;i<=N;i++) I.s[1][i]=f[i+TN*N];
G.n=G.m=N;
for(i=1;i<=N;i++){
SPFA(c,i,TA_NUMS,f);
for(j=1;j<=N;j++) G.s[i][j]=f[j+N];
}
}
inline int left(int up,int fr){//这个状态的骰子(上面是up,前面是fr),左边是哪个面
return onleft[up][fr];
}
inline int right(int up,int fr){
return opposite[onleft[up][fr]];//这个状态的骰子,右面是哪个面
}
void maketa(void){//得到"尝试区"的邻接表,"ta"就是尝试区
int x,y,up,fr,u,v;
TA_NUMS=SIZECIR*N;//一列的状态数是N,共SIZECIR列
for(x=0;x<SIZECIR;x++){
for(y=1;y<=SIZEH;y++){
for(up=1;up<=NUMSIDE;up++){
for(fr=1;fr<=NUMSIDE;fr++){
if(up==fr||opposite[up]==fr) continue;
u=statelis[y][up][fr]+x*N;//对不同行的状态进行"连续编号"
if(x>0){//向左滚,右变上,前不变
v=statelis[y][right(up,fr)][fr]+(x-1)*N;
c[u].push_back(make_pair(v,sticker[right(up,fr)]));
}
if(x<SIZECIR-1){//向右滚,左变上,前不变
v=statelis[y][left(up,fr)][fr]+(x+1)*N;
c[u].push_back(make_pair(v,sticker[left(up,fr)]));
}
if(y<SIZEH){//向上滚,前变上,下变前
v=statelis[y+1][fr][opposite[up]]+x*N;
c[u].push_back(make_pair(v,sticker[fr]));
}
if(y>1){//向下滚,后变上,上变前
v=statelis[y-1][opposite[fr]][up]+x*N;
c[u].push_back(make_pair(v,sticker[opposite[fr]]));
}
}
}
}
}
}
void init(void){
int i,j,k,x1,x2,y1,y2,tot=0;
for(i=1;i<=NUMSIDE;i++) scanf("%d",&sticker[i]);
opposite[1]=6,opposite[6]=1;
opposite[2]=5,opposite[5]=2;
opposite[3]=4,opposite[4]=3;
for(i=1;i<=SIZEH;i++){//这里得出了所有的状态
for(j=1;j<=NUMSIDE;j++){
for(k=1;k<=NUMSIDE;k++){
if(j==k||opposite[j]==k) continue;
tot++;
state[tot]=make_pair(i,make_pair(j,k));
statelis[i][j][k]=tot;
}
}
}
N=tot;//合法的状态总数
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>x2){//将棋盘水平旋转180度
//上下不变
swap(sticker[2],sticker[5]);//前后交换,即2和5对调
swap(sticker[3],sticker[4]);//左右交换,即3和4对调
swap(x1,x2);//横坐标交换
y1=SIZEH+1-y1,y2=SIZEH+1-y2;//纵坐标翻折
}
if(x1!=0) x2-=x1,x1=0;//平移至最左边
delta=x2-x1;
S=statelis[y1][1][2];//最开始1号面朝上,2号面朝前
tot=0;
for(i=1;i<=NUMSIDE;i++){
for(j=1;j<=NUMSIDE;j++){
if(i==j||opposite[i]==j) continue;
T.push_back(statelis[y2][i][j]);//纵坐标为y2,每一种状态都有可能
}
}
onleft[1][2]=3,onleft[1][3]=5;
onleft[2][1]=4,onleft[2][3]=1;
onleft[3][1]=2,onleft[3][2]=6;
for(i=1;i<=NUMSIDE;i++){
for(j=1;j<=NUMSIDE;j++){
if(i==j||opposite[i]==j) continue;
if(onleft[i][j]) continue;
else if(onleft[i][opposite[j]]) onleft[i][j]=opposite[onleft[i][opposite[j]]];
else if(onleft[opposite[i]][j]) onleft[i][j]=opposite[onleft[opposite[i]][j]];
else if(onleft[opposite[i]][opposite[j]]) onleft[i][j]=onleft[opposite[i]][opposite[j]];
}
}
//至此生成了onleft数组,由此可以轻松得到某个状态下骰子所有位置的面都是什么
}
void work(void){
maketa();
MATRIX G,I;
makegraph(I,G);
I=I*quickpow(G,delta);
ll ans=INF;
for(int i=0;i<T.size();i++) ans=min(ans,I.s[1][T[i]]);
cout<<ans<<endl;
}
int main(){
freopen("dicecontest.in","r",stdin);
freopen("dicecontest.out","w",stdout);
init();
work();
return 0;
}