变态的最短路，害我写了很多行。
CO
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-3-16
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <sstream>
using std::stringstream;
#include <vector>
using std::vector;
#include <string>
using std::string;
#include <stack>
using std::stack;
#include <queue>
using std::queue;
#include <map>
using std::map;
using std::pair;
using std::make_pair;
#include <algorithm>
using std::sort;
#include <cassert>
//using std::assert;
struct Cube
{
int left,right,top,forward,bottom,backward;
inline
void swap(int& a,int& b,int& c,int& d)
{
int s=a;
a=b;
b=c;
c=d;
d=s;
}
inline
void goup()
{
swap(bottom,backward,top,forward);
}
inline
void godown()
{
swap(bottom,forward,top,backward);
}
inline
void goright()
{
swap(bottom,right,top,left);
}
inline
void goleft()
{
swap(bottom,left,top,right);
}
};
struct Compare
{
bool operator()(const pair<pair<Cube,pair<int,int> >,int>& a,
const pair<pair<Cube,pair<int,int> >,int>& b)
{
return a.second>b.second;
}
};
class Application
{
static const int SIDE=6;
static const int top=0,
bottom=SIDE-1-top,
left=1,
right=SIDE-1-left,
forward=2,
backward=SIDE-1-forward;
static const int SIZE=8;
static const int ID=24;
static const int oo=1<<29;
pair<int,int> f,t;
vector<int> get_point;
vector<vector<int> > get_id;
public:
Application()
:get_point(SIDE),get_id(SIDE,vector<int>(SIDE))
{
char x,y;
cin>>x>>y;
f.first=x-‘a’;
f.second=y-‘1’;
cin>>x>>y;
t.first=x-‘a’;
t.second=y-‘1’;
//forward, backward, top, right, bottom and left
cin>>get_point[forward]
>>get_point[backward]
>>get_point[top]
>>get_point[right]
>>get_point[bottom]
>>get_point[left];
}
int run()
{
//init get_id
for (int i=0,id=0;i<SIDE;i++)
for (int j=0;j<SIDE;j++)
if ((j!=i)&&(j+i+1!=SIDE))
get_id[i][j]=id++;
//dijkstra
typedef pair<pair<int,int>,int> pre_type;
vector<vector<vector<int> > >
dist(SIZE,vector<vector<int> >(SIZE,vector<int>(ID,oo)));
vector<vector<vector<pre_type> > >
pre(SIZE,vector<vector<pre_type> >(SIZE,vector<pre_type>(ID)));
std::priority_queue<pair<pair<Cube,pair<int,int> >,int>,
vector<pair<pair<Cube,pair<int,int> >,int> >,
Compare> q;
//push start state
Cube start;
start.top=top;
start.bottom=bottom;
start.left=left;
start.right=right;
start.forward=forward;
start.backward=backward;
q.push(make_pair(make_pair(start,f),get_point[start.bottom]));
while (!q.empty())
{
pair<pair<Cube,pair<int,int> >,int> now=q.top();
#define getdist(who) (dist[who.first.second.first]\
[who.first.second.second]\
[get_id[who.first.first.top]\
[who.first.first.left]]\
)
if (getdist(now)==oo)
{
getdist(now)=now.second;
#define assignpre(dir,dx,dy)\
from.first.first=now.first.first;\
from.first.first.go##dir();\
from.first.second=make_pair(now.first.second.first+(dx),\
now.first.second.second+(dy));\
if ((from.first.second.first>=0)\
&&(from.first.second.first<SIZE)\
&&(from.first.second.second>=0)\
&&(from.first.second.second<SIZE)\
&&(getdist(from)+get_point[now.first.first.bottom]==now.second))\
{\
pre[now.first.second.first]\
[now.first.second.second]\
[get_id[now.first.first.top]\
[now.first.first.left]]\
=make_pair(from.first.second,\
get_id[from.first.first.top]\
[from.first.first.left]\
);\
}
pair<pair<Cube,pair<int,int> >,int> from;
assignpre(left,-1,0);
assignpre(right,1,0);
assignpre(up,0,1);
assignpre(down,0,-1);
#undef assignpre
#define letusgo(dir,dx,dy)\
go.first.first=now.first.first;\
go.first.first.go##dir();\
go.first.second=make_pair(now.first.second.first+(dx),\
now.first.second.second+(dy));\
if ((go.first.second.first>=0)\
&&(go.first.second.first<SIZE)\
&&(go.first.second.second>=0)\
&&(go.first.second.second<SIZE)\
&&(getdist(go)==oo))\
{\
go.second=now.second+get_point[go.first.first.bottom];\
q.push(go);\
}
pair<pair<Cube,pair<int,int> >,int> go;
letusgo(left,-1,0);
letusgo(right,1,0);
letusgo(up,0,1);
letusgo(down,0,-1);
#undef letusgo
}
if (now.first.second==t) break;
q.pop();
#undef getdist
}
stack<pre_type> s;
s.push(make_pair(q.top().first.second,
get_id[q.top().first.first.top]
[q.top().first.first.left]));
for (pre_type from=make_pair(f,get_id[start.top][start.left]);
s.top()!=from;)
{
pre_type getpre=pre[s.top().first.first]
[s.top().first.second]
[s.top().second];
s.push(getpre);
}
cout<<q.top().second<<” “;
while (!s.empty())
{
cout<<char(s.top().first.first+’a’)
<<char(s.top().first.second+’1′);
s.pop();
if (s.empty()) cout<<endl;
else cout<<” “;
}
return 0;
}
};
int main()
{
Application app;
return app.run();
}