洛谷 P2349 金字塔 题解

题目链接

题目描述

有一盗墓者潜入一金字塔盗宝。当她（难道是Lara Croft ?）打开一个宝箱的时候，突然冒出一阵烟（潘多拉的盒子？），她迅速意识到形势不妙，三十六计走为上计……由于她盗得了金字塔的地图，所以她希望能找出最佳逃跑路线。地图上标有N个室，她现在就在1室，金字塔的出口在N室。她知道一个秘密：那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线，使得在最坏的情况下所用的时间最少。

题解

这道题可以用A*来做

估价函数由两个值组成：该节点到终点的最短距离和当前已经经过路径的最大值（在代码里估价函数为g，实际距离为step，当前节点位置为x，已经经过路径的边权的最大值为maxx）

代码

#include < cstdio >
#include < cstring >
#include < algorithm >
#include < queue>
using namespace std;
const int maxn=100005;
struct Node
{int to,next,dis;
} edge[maxn<<1];
struct node
{int g,step,maxx,x;bool operator < (node xx) const{return xx.g<g;}
};
int k=0,head[maxn],n,m,a,b,c,dist[maxn];
bool visit[maxn];
void a

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！