题目链接
题意：题目大意：给你一张格子图，r 根横线， c 根竖线。告诉你起点和终点，然后从起点走，每条边有权值，如果是0，就表示无法通行。走的规则是（通俗点）：车子的惯性比较大，如果你在下个路口要转弯，那么后半段就开慢了，好转弯，转弯完了之后，你要加速，那么前半段就慢了，这两种情况都会使这段路的时间加倍，但是如果一条路同时是这样，那么也只算两倍。起点这终点一个启动，一个是制动，那么和他们相连的第一条边也算两倍。问你最短时间，如果不行，就输出 “Impossible” 。
解题思路：拆点。把一个点拆成8个点：上下左右，是否加倍
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 9e4 + 5;
const int UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3;
const int inv[] = { 1, 0, 3, 2 };
const int dr[] = { -1, 1, 0, 0};
const int dc[] = { 0, 0, -1, 1};
const int maxc = 105, maxr = 105;
int grid[maxr][maxc][4];
int n, id[maxr][maxc][4][2];
int R, C;
int ID(int r, int c, int dir, int doubled){int &x = id[r][c][dir][doubled];if( !x ) x=++n;return x;
}
bool cango(int r, int c, int dir){if( r<0 || r>=R || c<0 || c>=C ) return false;return grid[r][c][dir]>0;
}
struct Edge{int u, v, w;Edge(int u,int v,int w):u(u),v(v),w(w){}
};
struct HeapNode{int dist,u;bool operator<(const HeapNode& rhs) const {return dist>rhs.dist;}
};
struct Dijkstra{int n, m;bool done[N];int d[N];vector<Edge> edges;vector<int> G[N];void init(int n){this->n=n;for ( int i=1; i<=n; i++ ) G[i].clear();edges.clear();}void addeage(int u, int v, int w){edges.push_back(Edge(u,v,w));m=edges.size();G[u].push_back(m-1);}#define Inf 0x3f3f3f3fvoid dijkstra(int s){for ( int i=1; i<=n; i++ ) done[i]=0, d[i]=Inf;d[s]=0;priority_queue<HeapNode> Q;Q.push((HeapNode){
0,s});while( !Q.empty() ){HeapNode x=Q.top(); Q.pop();int u=x.u;if( done[u] ) continue;done[u]=1;for ( int i=0; i<G[u].size(); i++ ){Edge& e=edges[G[u][i]];if( d[e.v]>d[u]+e.w ){d[e.v]=d[u]+e.w;Q.push((HeapNode){d[e.v],e.v});}}}}
};Dijkstra D;
inline int read(){int x=0, f=1; char ch=getchar();while( !isdigit(ch) ) { if( ch=='-' ) f=-1; ch=getchar(); }while( isdigit(ch) ) { x=x*10+ch-'0'; ch=getchar(); }return x*f;
}
int main(){int r1, c1, r2, c2, kase=0;while( scanf("%d%d%d%d%d%d", &R, &C, &r1, &c1, &r2, &c2 ) == 6 && R ){r1--, r2--, c1--, c2--;for ( int r=0; r<R; r++ ){for ( int c=0; c<C-1; c++ )grid[r][c][RIGHT]=grid[r][c+1][LEFT]=read();if( r!=R-1 )for ( int c=0; c<C; c++ )grid[r][c][DOWN]=grid[r+1][c][UP]=read();}D.init(R*C*8+5);n=1;memset(id,0,sizeof(id));for ( int dir=0; dir<4; dir++ ) if( cango(r1,c1,dir) )D.addeage(1,ID(r1+dr[dir],c1+dc[dir],dir,1),grid[r1][c1][dir]*2);for ( int r=0; r<R; r++ )for ( int c=0; c<C; c++ )for ( int dir=0; dir<4; dir++ )if( cango(r,c,inv[dir]) ) for ( int newdir=0; newdir<4; newdir++ )if( cango(r,c,newdir) )for ( int doubled=0; doubled<2; doubled++ ){int newr=r+dr[newdir];int newc=c+dc[newdir];int v=grid[r][c][newdir], newdoubled=0;if( dir!=newdir ){if( !doubled ) v+=grid[r][c][inv[dir]];newdoubled=1; v+=grid[r][c][newdir]; }D.addeage(ID(r,c,dir,doubled),ID(newr,newc,newdir,newdoubled),v); }D.dijkstra(1);int ans=Inf;for ( int dir=0; dir<4; dir++ )if( cango(r2,c2,inv[dir] ) )for ( int doubled=0; doubled<2; doubled++ ){int v=D.d[ID(r2,c2,dir,doubled)];if(!doubled) v+=grid[r2][c2][inv[dir]];ans=min(v,ans); } printf("Case %d: ", ++kase );if( ans==Inf ) printf("Impossible\n");else printf("%d\n", ans);}
}