解题:SDOI 2010 魔法猪学院
2024-10-16 15:24:07
题外话:神**可持久化左偏树,你谷的人都太神了,学不来
我把这个当做A*模板题的说,先讲一讲个人对A*的理解:如果说普通的BFS是Bellman_Ford,那A*就是一个Dijkstra。以寻找第$k$优解为例,本来我们是要搜$k$遍;现在我们给当前的实际代价加上一个估计的乐观代价,这个就叫做估价函数;以每个状态的估价函数为标准,用堆维护每个状态就能保证当前的到的一定是还能得到的最优解,这样一次搜索就可以得到答案。
这里用每个点到达终点的距离作为估价函数即可
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=;
struct a
{
int node;
double dist;
};
bool operator < (a x,a y)
{
return x.dist>y.dist;
}
priority_queue<a> hp;
int p[N],noww[M],goal[M];
int P[N],Noww[M],Goal[M];
double val[M],Val[M],dis[N];
int n,m,t1,t2,cnt,Cnt,ans;
double e,t3;
bool vis[N];
void link1(int f,int t,double v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v;
}
void link2(int f,int t,double v)
{
Noww[++Cnt]=P[f],P[f]=Cnt;
Goal[Cnt]=t,Val[Cnt]=v;
}
void Dijkstra(int s)
{
for(int i=;i<=n;i++) dis[i]=2e9;
dis[n]=,hp.push((a){n,dis[n]});
while(!hp.empty())
{
a tt=hp.top(); hp.pop(); int tn=tt.node;
if(vis[tn]) continue; vis[tn]=true;
for(int i=P[tn];i;i=Noww[i])
if(dis[Goal[i]]>dis[tn]+Val[i])
dis[Goal[i]]=dis[tn]+Val[i],hp.push((a){Goal[i],dis[Goal[i]]});
}
}
void Astar(int s)
{
hp.push((a){,dis[]});
while(!hp.empty())
{
a tn=hp.top(); hp.pop();
double d=tn.dist-dis[tn.node];
if(tn.node==n)
{
if(e<d) return ;
else e-=d,ans++;
}
for(int i=p[tn.node];i;i=noww[i])
hp.push((a){goal[i],d+val[i]+dis[goal[i]]});
}
}
void SPJ()
{
if(e==1e7)//有毒啊
printf(""),exit();
}
int main ()
{
scanf("%d%d%lf",&n,&m,&e),SPJ();
for(int i=;i<=m;i++)
{
scanf("%d%d%lf",&t1,&t2,&t3);
link1(t1,t2,t3),link2(t2,t1,t3);
}
Dijkstra(n),Astar();
printf("%d",ans);
return ;
}
最新文章
- left join 多个表关联时,将表值置换
- 转:MyBean的安装
- Find the equipment indices
- uva 297 quadtrees——yhx
- Activity启动方式
- BootStrap入门_创建第一个例子
- Java基础之IO框架
- ssh框架知识点回顾
- 读取xml文件中节点
- IDEA 编译 Jmeter 4.0 ( 二次开发_1 )
- ZJOI 2019 划水记
- mysql可以远程连接的配置
- PHP 正则 空字符 / NUL字符
- redis,缓存雪崩,粗粒度锁,缓存一致性
- Vim 常用配置及插件安装使用
- web自动化测试---web页面元素的定位
- 记一次排查局网内的ARP包 “不存在的” MAC 地址及 “不存在的”IP 所发的ARP包
- 【JEECG技术文档】JEECG部门管理员操作手册
- c# 导出text 文本文件
- CVE-2010-2553 Microsoft Windows Cinepak 编码解码器解压缩漏洞 分析
热门文章
- 大牛都是这样写测试用例的,你get到了嘛?
- Spark计算模型RDD
- comet4j推送 405/500 JSON转换异常
- Buaaclubs项目介绍
- gogoing软件NABCD
- Oracle 的四种连接-左外连接、右外连接、内连接、全连接
- ns-3 可视化模拟 (一) PyViz
- 树莓派与Arduino Leonardo使用NRF24L01无线模块通信之基于RF24库 (五) 树莓派单子节点发送数据
- Beta阶段DAY1
- [转]无需看到你的脸就能认出你——实现Beyond Frontal Faces: Improving Person Recognition Using Multiple Cues