题意：一张网格图，多组数据，输入n,m,sx,sy,tx,ty大小，起终点
接下来共有2n-1行，奇数行有m-1个数，表示横向的边权，偶数行有m个数，表示纵向的边权
样例输入：
4 4 1 1 4 4
10 10 10
9 0 0 10
0 0 0
9 0 0 10
0 9 0 10
0 9 9
2 2 1 1 2 2
0
1 1
0
0 0 0 0 0 0
样例输出：
Case 1: 100
Case 2: Impossible
我们发现此题的特点在于允许转向，也就是说我们可以将转向的状态利用一维表示出来以进行转移
同时由于起终点也需要*2，我们干脆新开两维，一维表示是否*2，另一维表示当前已经操作后面对的方向
利用spfa进行转移即可
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std;
const int NN=;
const int NNN=;
const int inf=;
inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;} int g[NN][];
int d[NNN];
bool vis[NNN]; int dx[]={,,,-};
int dy[]={,-,,}; int n,m,sx,sy,tx,ty,x,y,t,idx,w;
struct node{int x,y,t;};queue<node> q; inline int calc(int x,int y){return (x-)*m+(y-);}
inline int calc(int x,int y,int t){return calc(x,y)*+t;}
bool check(int x,int y){return <=x&&x<=n&&<=y&&y<=m;} int main(){
while(scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&tx,&ty)!=EOF&&n&&m){ rep(i,,*n-)
if(i&) rep(y,,m-){
x=(i+)/,w=read();if(!w) w=inf;
g[calc(x,y)][]=g[calc(x,y+)][]=w;}
else rep(y,,m){
x=i/,w=read();if(!w) w=inf;
g[calc(x,y)][]=g[calc(x+,y)][]=w;}
//t代表的状态是身后已经加的边的状态 memset(d,,sizeof d);
d[calc(sx,sy,)]=;
vis[calc(sx,sy,)]=;
q.push((node){sx,sy,}); while(!q.empty()){
x=q.front().x;
y=q.front().y;
t=q.front().t;q.pop();
vis[calc(x,y,t)]=; // 4 前后都要二倍
if(t<){// i-i
int xx=x+dx[t],yy=y+dy[t];
if(!check(xx,yy)) continue;
int w=g[calc(x,y)][t];
if(d[calc(xx,yy,t)]>d[calc(x,y,t)]+w){
d[calc(xx,yy,t)]=d[calc(x,y,t)]+w;
if(!vis[calc(xx,yy,t)])
vis[calc(xx,yy,t)]=,q.push((node){xx,yy,t});}
w=w*;//i-4
if(d[calc(xx,yy,)]>d[calc(x,y,t)]+w){
d[calc(xx,yy,)]=d[calc(x,y,t)]+w;
if(!vis[calc(xx,yy,)])
vis[calc(xx,yy,)]=,q.push((node){xx,yy,});}
}else{
for(int i=;i<=;i++){
int xx=x+dx[i],yy=y+dy[i];
if(!check(xx,yy)) continue;
int w=g[calc(x,y)][i]*; //4 是转向所以w跟随i变化
// 4-i
if(d[calc(xx,yy,i)]>d[calc(x,y,t)]+w){
d[calc(xx,yy,i)]=d[calc(x,y,t)]+w;
if(!vis[calc(xx,yy,i)])
vis[calc(xx,yy,i)]=,q.push((node){xx,yy,i});}
// 4-4
if(d[calc(xx,yy,)]>d[calc(x,y,t)]+w){
d[calc(xx,yy,)]=d[calc(x,y,t)]+w;
if(!vis[calc(xx,yy,)])
vis[calc(xx,yy,)]=,q.push((node){xx,yy,});
}
}
}/*
i-i 正常直走
i-4 决策 转弯的第一条边
到达终点
4-i 决策 转弯的第二条边
起点结束
4-4 决策 转弯到终点
决策 连续转弯
*/
}// 三维状态 二维权值
int ans=d[calc(tx,ty,)];
if(ans>=inf) printf("Case %d: Impossible\n",++idx);
else printf("Case %d: %d\n",++idx,ans);
}return ;
}
完结撒花