UVALive 4128 Steam Roller 蒸汽式压路机（最短路，变形） WA中。。。。。
2024-10-20 16:19:51
题意：
给一个由n*m个正方形格子组成的矩形，其中每个格子的边都是可以走的，长度给定，规定：如果在进入该路前需要拐弯，或者走完该路需要拐弯，都是需要付出双倍距离的（每条路最多算2倍）。问从起点到终点的最短路经长。
思路：
这个题目超级难搞，思路很简单，就是很麻烦！！！我将1个点4个方向的路长都记录下来，然后进行最短路，只要一个点的某个方向更新了，就进队。所有都考虑得差不多了，就是WA。。。
步骤 :
（1）起点不进队，因为起点出发都需要双倍，况且，如果起点路长为0的话，其他点就不能路过起点了，所以将起点能更新到的点进队，并更新他们的路长，而起点路长仍然是INF。
（2）对于用一个点来更新别人，可以更新相邻4个方向的点，而更新某一个方向的点又可以用当前点的4个方向来更新它。
（3）一旦被更新的点是终点，就更新答案（出来也要双倍）。因为路径可能经过终点多次再折返从终点出来会更近。
（4）所以边注意不能算2倍以上。
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define pii pair<int,int>
#define LL unsigned long long
#define up 0
#define right 1
#define down 2
#define left 3
using namespace std;
const int N=;
int n, m, a, sx, sy, ex, ey;
int g[N][N][]; //0从12点钟开始，顺时针走
int dist[N][N][]; //记录来自4个方向的距离
int tag[N][N][]; //标记4个值是否已经翻倍了
int inq[N][N];
int ans;
bool ok(int x, int y)
{
if(x>&&x<=n && y>&&y<=m) return true;
else return false;
}
void isinq(deque<pii> &que, int x,int y)
{
if(!inq[x][y]) que.push_back(make_pair(x,y));
inq[x][y]=;
} void isend(int x,int y)
{
if(x==ex && y==ey)
{
if(dist[x][y][up]<INF)
ans=min(ans, dist[x][y][up]+(-tag[x][y][up])*g[x][y][down]);
if(dist[x][y][down]<INF)
ans=min(ans, dist[x][y][down]+(-tag[x][y][down])*g[x][y][up]);
if(dist[x][y][left]<INF)
ans=min(ans, dist[x][y][left]+(-tag[x][y][left])*g[x][y][right]);
if(dist[x][y][right]<INF)
ans=min(ans, dist[x][y][right]+(-tag[x][y][right])*g[x][y][left]);
}
} void init_start(deque<pii> &que)
{
int x=sx;
int y=sy;
if(ok(x-,y) && g[x][y][up] ) //上0
{
dist[x-][y][up] = *g[x][y][up] ;
tag[x-][y][up]=; //拐弯了，已经翻倍
isinq(que, x-, y );
isend(x-,y);
}
if(ok(x+,y) && g[x][y][down] ) //下2
{
dist[x+][y][down] = *g[x][y][down];
tag[x+][y][down]=;
isinq(que, x+, y );
isend(x+,y);
}
if(ok(x,y-) && g[x][y][left] ) //左3
{
dist[x][y-][left] = *g[x][y][left];
tag[x][y-][left]=;
isinq(que, x, y-);
isend(x,y-);
}
if(ok(x,y+) && g[x][y][right] ) //右1
{
dist[x][y+][right] = *g[x][y][right];
tag[x][y+][right]=;
isinq(que, x, y+);
isend(x,y+);
} } void spfa()
{
deque<pii> que;
init_start(que); while(!que.empty())
{
int x=que.front().first;
int y=que.front().second;
que.pop_front();
inq[x][y]=;
//每个点有4个方向
if(ok(x-,y) && g[x][y][up] ) //上0
{
if(dist[x][y][up]<INF && dist[x-][y][up]> dist[x][y][up] + g[x][y][up]) //上->上
{
dist[x-][y][up]= dist[x][y][up] + g[x][y][up];
tag[x-][y][up]=; //直走的，不计
isinq(que, x-, y );
}
if(dist[x][y][right]<INF && dist[x-][y][up]> dist[x][y][right] + (-tag[x][y][right])*g[x][y][left] + *g[x][y][up] ) //右->上
{
dist[x-][y][up]= dist[x][y][right] + (-tag[x][y][right])*g[x][y][left] + *g[x][y][up];
tag[x-][y][up]=; //拐弯了，已经翻倍
isinq(que, x-, y );
}
if(dist[x][y][left]<INF && dist[x-][y][up]> dist[x][y][left] + (-tag[x][y][left])*g[x][y][right] + *g[x][y][up] ) //左->上
{
dist[x-][y][up]= dist[x][y][left] + (-tag[x][y][left])*g[x][y][right] + *g[x][y][up];
tag[x-][y][up]=; //同上
isinq(que, x-, y );
}
if(dist[x][y][down]<INF && dist[x-][y][up]> dist[x][y][down] + (-tag[x][y][down])*g[x][y][up] + *g[x][y][up] ) //下-上
{
dist[x-][y][up]= dist[x][y][down] + (-tag[x][y][down])*g[x][y][up] + *g[x][y][up];
tag[x-][y][up]=;
isinq(que, x-, y);
}
isend(x-,y);
}
if(ok(x+,y) && g[x][y][down] ) //下2
{
if(dist[x][y][down]<INF && dist[x+][y][down] > dist[x][y][down] + g[x][y][down] ) //下->下
{
dist[x+][y][down] = dist[x][y][down] + g[x][y][down];
tag[x+][y][down]=;
isinq(que, x+, y );
}
if(dist[x][y][right]<INF && dist[x+][y][down] > dist[x][y][right] + (-tag[x][y][right])*g[x][y][left] + *g[x][y][down] ) //右->下
{
dist[x+][y][down] = dist[x][y][right] + (-tag[x][y][right])*g[x][y][left] + *g[x][y][down];
tag[x+][y][down]=;
isinq(que, x+, y );
}
if(dist[x][y][left]<INF && dist[x+][y][down] > dist[x][y][left] + (-tag[x][y][left])*g[x][y][right] + *g[x][y][down] ) //左->下
{
dist[x+][y][down] = dist[x][y][left] + (-tag[x][y][left])*g[x][y][right] + *g[x][y][down];
tag[x+][y][down]=;
isinq(que, x+, y);
}
if(dist[x][y][up]<INF && dist[x+][y][down] > dist[x][y][up] + (-tag[x][y][up])*g[x][y][down] + *g[x][y][down] ) //上-下
{
dist[x+][y][down] = dist[x][y][up] + (-tag[x][y][up])*g[x][y][down] + *g[x][y][down];
tag[x+][y][down]=;
isinq(que, x+, y);
}
isend(x+,y);
}
if(ok(x,y-) && g[x][y][left] ) //左3
{
if(dist[x][y][left]<INF && dist[x][y-][left] > dist[x][y][left] + g[x][y][left] ) //左->左
{
dist[x][y-][left] = dist[x][y][left] + g[x][y][left];
tag[x][y-][left]=;
isinq(que, x, y-);
}
if(dist[x][y][down]<INF && dist[x][y-][left] > dist[x][y][down] + (-tag[x][y][down])*g[x][y][up] + *g[x][y][left] ) //下->左
{
dist[x][y-][left] = dist[x][y][down] + (-tag[x][y][down])*g[x][y][up] + *g[x][y][left];
tag[x][y-][left]=;
isinq(que, x, y-);
}
if(dist[x][y][up]<INF && dist[x][y-][left] > dist[x][y][up] + (-tag[x][y][up])*g[x][y][down] + *g[x][y][left] ) //上->左
{
dist[x][y-][left] = dist[x][y][up] + (-tag[x][y][up])*g[x][y][down] + *g[x][y][left];
tag[x][y-][left]=;
isinq(que, x, y-);
}
if(dist[x][y][right]<INF && dist[x][y-][left] > dist[x][y][right] + (-tag[x][y][right])*g[x][y][left] + *g[x][y][left] ) //右-左
{
dist[x][y-][left] = dist[x][y][right] + (-tag[x][y][right])*g[x][y][left] + *g[x][y][left];
tag[x][y-][left]=;
isinq(que, x, y-);
}
isend(x,y-);
}
if(ok(x,y+) && g[x][y][right] ) //右1
{
if(dist[x][y][right]<INF && dist[x][y+][right] > dist[x][y][right] + g[x][y][right] ) //右->右
{
dist[x][y+][right] = dist[x][y][right] + g[x][y][right];
tag[x][y+][right]=;
isinq(que, x, y+);
}
if(dist[x][y][down]<INF && dist[x][y+][right] > dist[x][y][down] + (-tag[x][y][down])*g[x][y][up] + *g[x][y][right] ) //下->右
{
dist[x][y+][right] = dist[x][y][down] + (-tag[x][y][down])*g[x][y][up] + *g[x][y][right];
tag[x][y+][right]=;
isinq(que, x, y+);
}
if(dist[x][y][up]<INF && dist[x][y+][right] > dist[x][y][up] + (-tag[x][y][up])*g[x][y][down] + *g[x][y][right] ) //上->右
{
dist[x][y+][right] = dist[x][y][up] + (-tag[x][y][up])*g[x][y][down] + *g[x][y][right];
tag[x][y+][right]=;
isinq(que, x, y+);
} if(dist[x][y][left]<INF && dist[x][y+][right] > dist[x][y][left] + (-tag[x][y][left])*g[x][y][right] + *g[x][y][right] ) //左-右
{
dist[x][y+][right] = dist[x][y][left] + (-tag[x][y][left])*g[x][y][right] + *g[x][y][right];
tag[x][y+][right]=;
isinq(que, x, y+);
}
isend(x,y+);
}
}
} int cal()
{
memset(dist, 0x7f, sizeof(dist));
memset(tag, , sizeof(tag));
memset(inq, , sizeof(inq));
ans=INF;
spfa();
return ans==INF? : ans;
} int main()
{
//freopen("input.txt", "r", stdin);
int Case=;
while(scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &ex, &ey), n+m+sx+sy+ex+ey)
{
memset(g, , sizeof(g));
for(int x=; x<n; x++) //行号
{
for(int y=; y<m; y++) //列号
{
scanf("%d", &a);
g[x][y][right]=a; //右边1
g[x][y+][left]=a; //左边3
}
for(int y=; y<=m; y++)
{
scanf("%d", &a);
g[x][y][down]=a; //下2
g[x+][y][up]=a; //上0
}
}
for(int y=; y<m; y++)
{
scanf("%d", &a);
g[n][y][right]=a; //右
g[n][y+][left]=a; //左
} int aa=cal();
if(aa) printf("Case %d: %d\n",++Case, aa);
else printf("Case %d: Impossible\n", ++Case);
}
return ;
}
WA代码
最新文章
- IIS7/IIS7.5 二级域名伪静态设置方法
- Swift学习--闭包的简单使用(三)
- shell编程之sleep的运用
- Linux中.a,.la,.o,.so文件的意义和编程实现
- 字符排序（hdoj1106）
- building android/ubuntu-touch on 32bit machine
- python中使用递归实现反转链表
- 常用的当前时间（返回String类型）
- man scp
- mipush ionic3 线上push
- 使用 nodeJs 开发微信公众号（设置自动回复消息）
- AdPlus
- php一些简单的作业题
- Lodop打印控件里SET_PRINT_STYLE和SET_PRINT_STYLEA
- pip --version问题
- How to duplicate the records in a MongoDB collection
- 莫衷一是——i+++j 该怎样计算？
- webpack入门指南-step03
- SpringBoot之mongoTemplate的使用
- 前端案例分享（一）：CSS+JS实现流星雨动画