题目大意：给你一个棋盘，你需要控制棋子依次经过编号为1~n的所有点，棋子的可以是车，马，象，都依照国际象棋的行棋方式，每走一步消耗1单位时间，但每次更换棋子都需要额外1单位时间，求经过所有点需要的最少时间 ，如果多种方案需要的最少时间相同，输出更换棋子次数最少的那个
有的机房老人用了记忆化搜索，但写起来好像很蛋疼。神仙学弟phy想了一个多元最短路，简洁好写
每个点有三种状态，先暴力建边。
然后根据点的编号从小到大，以每个点为源点跑一次两元最短路
注意，不能在每个点都记录超级源点/汇点，因为这样做会让更换棋子的步骤失效！
所以，每当跑完某个点的最短路时，先记录当前下一个点的三种状态的花费，从下一个编号的点开始跑时，先清数组，再把上次记录的花费扔到起始状态里，再去跑这个点为源点的最短路
接下来就是多元最短路了，可以用重载运算符，比较好写
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define N 15 6 #define M 500 7 #define inf 66666666 8 using namespace std; 9 10 int n,cte,num; 11 int mp[N][N],id[N][N][4],head[M]; 12 int px[M],py[M]; 13 struct node{int d,w; 14 friend bool operator < (const node &s1,const node &s2){ 15 if(s1.d!=s2.d) return s1.d<s2.d; 16 else return s1.w<s2.w; 17 }node(int d,int w):d(d),w(w){} node(){} 18 }; 19 struct Edge{int to,nxt,d,w;}edge[M*50]; 20 void ae(int u,int v,int d,int w){ 21 cte++;edge[cte].to=v,edge[cte].nxt=head[u]; 22 edge[cte].d=d,edge[cte].w=w,head[u]=cte; 23 } 24 inline int check(int x,int y) 25 {return 1<=x&&x<=n&&1<=y&&y<=n;} 26 void Build_Edge() 27 { 28 int s0,s1,s2,s3,t1,t2,t3; 29 for(int i=1;i<=n;i++) 30 for(int j=1;j<=n;j++){ 31 s1=id[i][j][1],s2=id[i][j][2],s3=id[i][j][3]; 32 ae(s1,s2,1,1),ae(s2,s1,1,1),ae(s1,s3,1,1),ae(s3,s1,1,1),ae(s2,s3,1,1),ae(s3,s2,1,1); 33 for(int x=1;x<=n;x++){if(!check(i+x,j))break;t1=id[i+x][j][1],ae(s1,t1,1,0);} 34 for(int x=1;x<=n;x++){if(!check(i,j+x))break;t1=id[i][j+x][1],ae(s1,t1,1,0);} 35 for(int x=1;x<=n;x++){if(!check(i-x,j))break;t1=id[i-x][j][1],ae(s1,t1,1,0);} 36 for(int x=1;x<=n;x++){if(!check(i,j-x))break;t1=id[i][j-x][1],ae(s1,t1,1,0);} 37 38 for(int x=1;x<=n;x++){if(!check(i+x,j+x))break;t3=id[i+x][j+x][3],ae(s3,t3,1,0);} 39 for(int x=1;x<=n;x++){if(!check(i-x,j+x))break;t3=id[i-x][j+x][3],ae(s3,t3,1,0);} 40 for(int x=1;x<=n;x++){if(!check(i+x,j-x))break;t3=id[i+x][j-x][3],ae(s3,t3,1,0);} 41 for(int x=1;x<=n;x++){if(!check(i-x,j-x))break;t3=id[i-x][j-x][3],ae(s3,t3,1,0);} 42 43 if(check(i+1,j+2))t2=id[i+1][j+2][2],ae(s2,t2,1,0); 44 if(check(i+2,j+1))t2=id[i+2][j+1][2],ae(s2,t2,1,0); 45 if(check(i-1,j-2))t2=id[i-1][j-2][2],ae(s2,t2,1,0); 46 if(check(i-2,j-1))t2=id[i-2][j-1][2],ae(s2,t2,1,0); 47 if(check(i+1,j-2))t2=id[i+1][j-2][2],ae(s2,t2,1,0); 48 if(check(i+2,j-1))t2=id[i+2][j-1][2],ae(s2,t2,1,0); 49 if(check(i-1,j+2))t2=id[i-1][j+2][2],ae(s2,t2,1,0); 50 if(check(i-2,j+1))t2=id[i-2][j+1][2],ae(s2,t2,1,0); 51 } 52 53 } 54 node dis[M],lst[5];int use[M]; 55 node SPFA() 56 { 57 int s1,s2,s3,t1,t2,t3; 58 queue<int>q;node tmp; 59 for(int i=1;i<n*n;i++) 60 { 61 memset(dis,0x3f,sizeof(dis)); 62 memset(use,0,sizeof(use)); 63 s1=id[px[i]][py[i]][1]; 64 s2=id[px[i]][py[i]][2]; 65 s3=id[px[i]][py[i]][3]; 66 dis[s1]=lst[1],dis[s2]=lst[2],dis[s3]=lst[3]; 67 use[s1]=1,use[s2]=1,use[s3]=1; 68 q.push(s1),q.push(s2),q.push(s3); 69 while(!q.empty()) 70 { 71 int x=q.front();q.pop(); 72 tmp=dis[x]; 73 for(int j=head[x];j;j=edge[j].nxt){ 74 int v=edge[j].to; 75 tmp.d+=edge[j].d,tmp.w+=edge[j].w; 76 if(tmp<dis[v]){ dis[v]=tmp; 77 if(!use[v]) use[v]=1,q.push(v); 78 }tmp=dis[x]; 79 }use[x]=0; 80 } 81 t1=id[px[i+1]][py[i+1]][1]; 82 t2=id[px[i+1]][py[i+1]][2]; 83 t3=id[px[i+1]][py[i+1]][3]; 84 lst[1]=dis[t1],lst[2]=dis[t2],lst[3]=dis[t3]; 85 } 86 node ret;ret.d=inf,ret.w=inf; 87 s1=id[px[n*n]][py[n*n]][1]; 88 s2=id[px[n*n]][py[n*n]][2]; 89 s3=id[px[n*n]][py[n*n]][3]; 90 if(dis[s1]<ret) ret=dis[s1]; 91 if(dis[s2]<ret) ret=dis[s2]; 92 if(dis[s3]<ret) ret=dis[s3]; 93 return ret; 94 } 95 96 int main() 97 { 98 //freopen("t1.in","r",stdin); 99 scanf("%d",&n); 100 for(int i=1;i<=n;i++) 101 for(int j=1;j<=n;j++) 102 scanf("%d",&mp[i][j]),id[i][j][1]=++num,id[i][j][2]=++num, 103 id[i][j][3]=++num,px[mp[i][j]]=i,py[mp[i][j]]=j; 104 Build_Edge(); 105 node ret=SPFA(); 106 printf("%d %d ",ret.d,ret.w); 107 return 0; 108 }