| 记录编号 |
182872 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[CEPC 2003] 骰子游戏 |
最终得分 |
100 |
| 用户昵称 |
 mikumikumi |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.880 s |
| 提交时间 |
2015-08-29 10:37:38 |
内存使用 |
2.01 MiB |
显示代码纯文本
#include<cstdio>
#include<deque>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
const LL maxn=LL(1e17);
const int SIZEH=4,SIZENUM=6;
const int SIZEC=20;
int L[7];
int x1,x2;
int y3,y2;
LL f[3000];
int opposite[7]={0};//第i面的对面是什么
int id[5][SIZENUM+1][SIZENUM+1]={0};//状态编号,分别是行，正面，上面
int N;//总状态数
int C;//c的状态数
int S;//起始状态
int onleft[40][40]={0};
deque<pair<int,int> > c[3000];
pair<int,pair<int,int> > state[720];
deque<int> T;
void check_u(int u)
{
int tem=u%N;
if(u==0) u=N;
cout<<(u-1)/N<<" ";
cout<<state[tem].first<<" "<<state[tem].second.first<<" "<<state[tem].second.second<<endl;;
}
class miku
{
public:
int n,m;
LL s[160][160];
miku()
{
n=m=0;
for(int i=0;i<=144;i++)
for(int j=0;j<=144;j++)
s[i][j]=maxn;
}
void print()
{
cout<<n<<" "<<m<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<s[i][j]<<" ";//check_u(j);
}
cout<<endl;
}
cout<<endl;
}
void make(int a)
{
n=m=a;
for(int i=1;i<=n;i++)
s[i][i]=0;
}
};
inline miku operator * (miku a,miku b)
{
miku c;
c.n=a.n;c.m=b.m;
for(int i=1;i<=c.n;i++)
for(int j=1;j<=c.m;j++)
{
for(int k=1;k<=a.m;k++)
c.s[i][j]=min(c.s[i][j],a.s[i][k]+b.s[k][j]);
}
return c;
}
inline miku quickpow(miku a,LL b)
{
miku re;
re.make(a.n);
//re.print();
//cout<<b<<endl;
while(b)
{
if(b&1) re=re*a;
b>>=1;a=a*a;
}
//re.print();
return re;
}
void check_c()
{
for(int u=1;u<=C;u++)
{
check_u(u);
cout<<"to:"<<endl;
for(int i=0;i<c[u].size();i++)
{
check_u(c[u][i].first);
cout<<c[u][i].second<<endl;
}
cout<<endl;
}
}
void check_f()
{
check_u(S);
for(int i=1;i<=N;i++) {check_u(i+8*N);cout<<" "<<f[i+8*N]<<endl;}
}
int left(int j,int k)
{
return onleft[j][k];
}
int right(int j,int k)
{
return opposite[onleft[j][k]];
}
void make_c()
{
C=SIZEC*N;
for(int x=0;x<SIZEC;x++)
for(int y=1;y<=4;y++)
for(int fr=1;fr<=6;fr++)//枚举正面
for(int up=1;up<=6;up++)
{
if(fr==up||fr==opposite[up]) continue;
int u=id[y][fr][up]+x*N;;
if(x>0) c[u].push_back(make_pair(id[y][fr][right(fr,up)]+(x-1)*N,L[right(fr,up)]));
if(x<SIZEC-1) c[u].push_back(make_pair(id[y][fr][left(fr,up)]+(x+1)*N,L[left(fr,up)]));
if(y>1) c[u].push_back(make_pair(id[y-1][up][opposite[fr]]+x*N,L[opposite[fr]]));
if(y<4) c[u].push_back(make_pair(id[y+1][opposite[up]][fr]+x*N,L[fr]));
}
//check_c();
}
void prepare()
{
opposite[1]=6;opposite[6]=1;
opposite[2]=5;opposite[5]=2;
opposite[4]=3;opposite[3]=4;
if(x1>x2)//镜像反转
{
swap(L[2],L[5]);
swap(L[3],L[4]);
swap(x1,x2);
y3=4+1-y3;y2=4+1-y2;
}
if(x1!=0) x2-=x1;x1=0;
N=0;
for(int i=1;i<=4;i++)
for(int j=1;j<=6;j++)
for(int k=1;k<=6;k++)
{
if(j==k||j==opposite[k]) continue;
id[i][j][k]=++N;
state[N]=make_pair(i,make_pair(j,k));
}
S=id[y3][2][1];
onleft[1][2]=4;onleft[1][3]=2;
onleft[2][1]=3;onleft[2][3]=6;
onleft[3][1]=5;onleft[3][2]=1;
for(int i=1;i<=6;i++)
for(int j=1;j<=6;j++)
{
if(i==j||i==opposite[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]];
}
make_c();
for(int i=1;i<=6;i++)
for(int j=1;j<=6;j++)
{
if(i==j||i==opposite[j]) continue;
T.push_back(id[y2][i][j]);
}
}
void spfa(int s,int n)
{
bool inq[3000]={0};
deque<int> Q;
for(int i=1;i<=n;i++) f[i]=maxn;
inq[s]=1;f[s]=0;Q.push_back(s);
//check_c();
while(!Q.empty())
{
int x=Q.front();Q.pop_front();inq[x]=0;
for(int i=0;i<c[x].size();i++)
{
pair<int,int> v=c[x][i];
if(f[x]+v.second<f[v.first])
{
f[v.first]=f[x]+v.second;
if(!inq[v.first])
{
Q.push_back(v.first);
inq[v.first]=1;
}
}
}
}
}
void get(miku &I,miku &D)
{
I.n=1;I.m=N;
int tem=SIZEC/2-1;
//cout<<N<<endl;
spfa(S+tem*N,C);
D.m=D.n=N;
//for(int i=1;i<=C;i++) cout<<f[i]<<endl;
for(int i=1;i<=N;i++) I.s[1][i]=f[i+tem*N];
for(int i=1;i<=N;i++)
{
spfa(i,C);
for(int j=1;j<=N;j++)
D.s[i][j]=f[j+N];
}
}
void work()
{
miku I,D;
get(I,D);
//D.print();
I=I*quickpow(D,x2-x1);
LL ans=maxn;
for(int i=0;i<T.size();i++)
{
ans=min(I.s[1][T[i]],ans);
}
cout<<ans;
}
int main()
{
freopen("dicecontest.in","r",stdin);
freopen("dicecontest.out","w",stdout);
for(int i=1;i<=6;i++)
scanf("%d",&L[i]);
scanf("%d%d%d%d",&x1,&y3,&x2,&y2);//lld
prepare();
//cout<<1<<endl;
work();
return 0;
}