题目描述：二维字符矩阵上有一船, ‘ ‘表示可走, ‘#’反之, ‘*’表示漩涡, 船每走"一格"消耗1单位A燃料,
船可以冲刺, 每次冲刺消耗perb单位的B燃料, 有两种冲刺方式, 一种是前方d个单位直线上没有’#'或’*', 直接冲到前方d格处,
另一种是前方临近格有漩涡, 冲刺进入此漩涡. 进漩涡只能靠冲刺, 现在A燃料无限, B燃料为b,
问最小消耗下的到达终点的"行动次数", 最小消耗的定义优先级有高到低分别是: 进入漩涡次数最少, A消耗最少, 行动次数最少.
解题报告：
对每个点的行动方案可行性做预处理, 然后用三维状态, 三维距离的Dijkstra做最短路. 其实把题目读懂,
做过二维Dijkstra的同学应该多少有点感觉了, 本题就是个三维状态的最短路:
dis[i][j][k]表示到i行j列冲刺了k次的最小耗费.
而这个"最小耗费"的定义也是三维的, 即:
1. 进入漩涡的次数.
2. A的消耗.
3. 行动次数.
而这个耗费大可不必用结构体来表示, 直接设INCU = 1000000, INCA = 1000,
其中INCU表示进一次漩涡的基数, INCA表示消耗一单位A的基数, 而行动次数的基数则是1,
这样它们的优先级也就由一个int型表示出来了. 然后设置冲刺次数上限为min{b/perb,
r*c}即可(因为冲刺次数显然不会大于格子总数). 每次状态扩展的时候判断一下冲刺次数是否满足要求即可.
上文转自：http://www.answeror.com/archives/28350
限制条件最短路伪代码：
地图的状态找好，如dis[i][j][k]，对应的有vst[i][j][k]
int judge(int i, int j, int k){return 最短路函数值;}
int dij()
{
dis = Max, vst = false; heap;//优先队,按judge排
dis[start_i][start_j][start_k] = 0;
heap.push(start_i, start_j, start_k);
result = -1;
while(!heap.empty())
{
now = heap.top() ; heap.pop();
if (now == finish) {result = now; break;}
vst[now] = 1;
for(遍历所有从now的可达状态next)
{
if (!vst[next] && dis[now] + value
< dis[next])
{
dis[next] = dis[now] + value;
if(!vst[next]) heap.push(next);
}
}
}
return result;
}
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define inf 0x7fffffff
#define A 1000000
#define B 1000
#define C 1
int d[20][20][400], vst[20][20][400], energy, per, n, m, dd, z,
t;
int move[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
char g[21][21];
struct jeo
{
int x, y,
z;
jeo(int x,
int y, int z):x(x), y(y), z(z){}
friend bool
operator < (jeo a, jeo b){return d[a.x][a.y][a.z]
> d[b.x][b.y][b.z];}
};
int judge(int a, int b, int c)
{
return a * A
+ b * B + c * C;
}
int dij(int stax, int stay, int tox, int toy)
{
for(int i =
0; i < n; i++)
for(int j = 0; j < m; j++)
for(int k = 0; k <= z; k++) d[i][j][k] = inf,
vst[i][j][k] = 0;
d[stax][stay][0] = judge(0, 0, 0);
priority_queue<jeo> heap;
heap.push(jeo(stax, stay, 0)); int ans = -1;
while(!heap.empty())
{
jeo tmp = heap.top(); heap.pop();
if (tmp.x == tox && tmp.y ==
toy){ans = d[tmp.x][tmp.y][tmp.z] % 1000; break;}
if (vst[tmp.x][tmp.y][tmp.z]) continue;
vst[tmp.x][tmp.y][tmp.z] = 1;
int a = d[tmp.x][tmp.y][tmp.z] / 1000000, b =
(d[tmp.x][tmp.y][tmp.z] % 1000000) / 1000, c =
d[tmp.x][tmp.y][tmp.z] % 1000;
for(int i = 0; i < 4; i++)
{
int tmpa = tmp.x + move[i][0], tmpb = tmp.y + move[i][1];
if (tmpa >= 0 &&
tmpa < n && tmpb
>= 0 && tmpb
< m && g[tmpa][tmpb]
!= '#')
{
if (g[tmpa][tmpb] == '*' && tmp.z +
1 <= z
&& !vst[tmpa][tmpb][tmp.z + 1]
&& judge(a + 1, b + 1, c + 1)
< d[tmpa][tmpb][tmp.z + 1])
d[tmpa][tmpb][tmp.z + 1] = judge(a + 1, b + 1, c + 1),
heap.push(jeo(tmpa, tmpb, tmp.z + 1));
else if (g[tmpa][tmpb] != '*' &&
!vst[tmpa][tmpb][tmp.z] && judge(a,
b + 1, c + 1) < d[tmpa][tmpb][tmp.z])
d[tmpa][tmpb][tmp.z] = judge(a, b + 1, c + 1), heap.push(jeo(tmpa,
tmpb, tmp.z));
}
bool flag = true;
加载中…