题目传送门 拆点神题。 1.拆成5个点，分别判定每个点未来的走向。 2.拆成8个点，从哪里来（4），是否加速（2），枚举后继状态。 两种最短路的写法。
注意原题为多组数据！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<stack>
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define INF 2100000000
#define ll long long
#define NAME "roller"
using namespace std;
const int UP=
0,LEFT=
1,DOWN=
2,RIGHT=
3;
const int inv[]={
2,
3,
0,
1};
const int dr[]={-
1,
0,
1,
0};
const int dc[]={
0,-
1,
0,
1};
const int maxr =
500;
const int maxc =
500;
const int maxn =
60000;
int n,grid[maxr][maxc][
4];
struct Edge{
int from,to,dist;
Edge(
int u,
int v,
int d):from(u),to(v),dist(d){}
};
struct SPFA{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
int d[maxn];
int p[maxn];
void init(
int n){
this->n=n;
for(
int i=
0;i<n;i++)G[i].clear();
edges.clear();
}
void AddEdge(
int from,
int to,
int dist){
edges.push_back(Edge(from,to,dist));
m=edges.size();
G[from].push_back(m-
1);
}
void spfa(
int s){
queue<int> Q;
memset(done,
0,
sizeof(done));
for(
int i=
0;i<n;i++)d[i]=INF;
d[s]=
0;
done[s]=
1;
Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();
done[u]=
0;
for(
int i=
0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(d[u]<INF&&d[e.to]>d[u]+e.dist){
d[e.to]=d[u]+e.dist;
p[e.to]=G[u][i];
if(!done[e.to]){
Q.push(e.to);
done[e.to]=
1;
}
}
}
}
}
};
int R,C;
bool cango(
int r,
int c,
int dir){
if(r<
0||r>R||c<
0||c>=C)
return 0;
return grid[r][c][dir]>
0;
}
SPFA solver;
int readint(){
int x;
scanf(
"%d",&x);
return x;
}
int id[maxr][maxc][
4][
2];
int ID(
int r,
int c,
int dir,
int doubled){
int &x=id[r][c][dir][doubled];
if(x==
0)x=++n;
return x;
}
int main(){
freopen(NAME
".in",
"r",stdin);
freopen(NAME
".out",
"w",stdout);
int r1,c1,r2,c2;
scanf(
"%d%d%d%d%d%d",&R,&C,&r1,&c1,&r2,&c2);
r1--;c1--;r2--;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]=readint();
}
if(r!=R-
1){
for(
int c=
0;c<C;c++){
grid[r][c][DOWN]=grid[r+
1][c][UP]=readint();
}
}
}
solver.init(R*C*
8+
1);
n=
0;
memset(id,
0,
sizeof(id));
for(
int dir=
0;dir<
4;dir++){
if(cango(r1,c1,dir))
solver.AddEdge(
0,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];
}
solver.AddEdge(ID(r,c,dir,doubled),ID(newr,newc,newdir,newdoubled),v);
}
}
}
}
}
solver.spfa(
0);
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=solver.d[ID(r2,c2,dir,doubled)];
if(!doubled)v+=grid[r2][c2][inv[dir]];
ans=min(ans,v);
}
}
if(ans==INF)
cout<<
"Impossible";
else cout<<ans;
return 0;
}
\\dijsktra
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<stack>
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define INF 2100000000
#define ll long long
#define NAME "roller"
using namespace std;
const int UP=
0,LEFT=
1,DOWN=
2,RIGHT=
3;
const int inv[]={
2,
3,
0,
1};
const int dr[]={-
1,
0,
1,
0};
const int dc[]={
0,-
1,
0,
1};
const int maxr =
500;
const int maxc =
500;
const int maxn =
60000;
int n,grid[maxr][maxc][
4];
struct Edge{
int from,to,dist;
Edge(
int u,
int v,
int d):from(u),to(v),dist(d){}
};
struct Dijkstra{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
int d[maxn];
int p[maxn];
void init(
int n){
this->n=n;
for(
int i=
0;i<n;i++)G[i].clear();
edges.clear();
}
void AddEdge(
int from,
int to,
int dist){
edges.push_back(Edge(from,to,dist));
m=edges.size();
G[from].push_back(m-
1);
}
struct HeapNode{
int d,u;
bool operator < (
const HeapNode &rhs)
const {
return d>rhs.d;
}
};
void dijkstra(
int s){
priority_queue<HeapNode> Q;
for(
int i=
0;i<n;i++)d[i]=INF;
d[s]=
0;
memset(done,
0,
sizeof(done));
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.to]>d[u]+e.dist){
d[e.to]=d[u]+e.dist;
p[e.to]=G[u][i];
Q.push((HeapNode){d[e.to],e.to});
}
}
}
}
};
int R,C;
bool cango(
int r,
int c,
int dir){
if(r<
0||r>R||c<
0||c>=C)
return 0;
return grid[r][c][dir]>
0;
}
Dijkstra solver;
int readint(){
int x;
scanf(
"%d",&x);
return x;
}
int id[maxr][maxc][
4][
2];
int ID(
int r,
int c,
int dir,
int doubled){
int &x=id[r][c][dir][doubled];
if(x==
0)x=++n;
return x;
}
int main(){
freopen(NAME
".in",
"r",stdin);
freopen(NAME
".out",
"w",stdout);
int r1,c1,r2,c2;
scanf(
"%d%d%d%d%d%d",&R,&C,&r1,&c1,&r2,&c2);
r1--;c1--;r2--;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]=readint();
}
if(r!=R-
1){
for(
int c=
0;c<C;c++){
grid[r][c][DOWN]=grid[r+
1][c][UP]=readint();
}
}
}
solver.init(R*C*
8+
1);
n=
0;
memset(id,
0,
sizeof(id));
for(
int dir=
0;dir<
4;dir++){
if(cango(r1,c1,dir))
solver.AddEdge(
0,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];
}
solver.AddEdge(ID(r,c,dir,doubled),ID(newr,newc,newdir,newdoubled),v);
}
}
}
}
}
solver.dijkstra(
0);
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=solver.d[ID(r2,c2,dir,doubled)];
if(!doubled)v+=grid[r2][c2][inv[dir]];
ans=min(ans,v);
}
}
if(ans==INF)
cout<<
"Impossible";
else cout<<ans;
return 0;
}
