POJ-1062 昂贵的聘礼---Dijkstra+枚举上界
2024-08-29 16:01:10
题目链接:
https://vjudge.net/problem/POJ-1062
题目大意:
中文题
思路:
1是终点,可以额外添加一个源点0,0到任意一节点的距离就是这个点的money,最终求的是d[1]最小值,但是由于有等级观念,所以必须枚举,每次枚举等级的上界,如果有不符合当前枚举的上界,就标记其不加入dijk算法中,然后跑一遍最短路,求出d[1],最终取d[1]的最小值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<sstream>
#define MEM(a, b) memset(a, b, sizeof(a));
using namespace std;
typedef long long ll;
const int maxn = + ;
const int INF = 0x3f3f3f3f;
int T, n, m, cases;//m是等级差
int Map[maxn][maxn];
int d[maxn], v[maxn];
struct node
{
int money, rank;
}cnt[maxn];
int dijkstra()
{
for(int i = ; i <= n; i++)d[i] = cnt[i].money;//假定的原点0,到每个点的距离就是它自己的价格
for(int i = ; i <= n; i++)
{
int x = , m = INF;
for(int i = ; i <= n; i++)if(!v[i] && m > d[i])m = d[x = i];//找出当前在集合中的最小距离
if(!x)break;//已经全部标记完毕
v[x] = ;
for(int i = ; i <= n; i++)
if(!v[i])d[i] = min(d[i], d[x] + Map[x][i]);//这里必须加上判断条件,因为有部分物品由于等级限制没有加入选项中
}
return d[];
}
int main()
{
cin >> m >> n;
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)Map[i][j] = INF;
MEM(cnt, );
MEM(v, );
int x, a, b;
for(int i = ; i <= n; i++)
{
cin >> cnt[i].money >> cnt[i].rank >> x;
while(x--)
{
cin >> a >> b;
Map[a][i] = b;//存图,存下从a到i的路径,这样就可以转化成求到点1的最短路径
}
}
int ans = INF;
for(int i = ; i <= n; i++)
{
int maxrank = cnt[i].rank;//枚举rank的上界
for(int j = ; j <= n; j++)
if(maxrank - cnt[j].rank > m || cnt[j].rank > maxrank)v[j] = ;
//事先标记好不符合条件的物品,如果有等级大于当前枚举的最大等级或者等级差超过m的标记,在dijk算法中不添加这些元素
else v[j] = ;
ans = min(ans, dijkstra());
}
cout<<ans<<endl;
return ;
}
最新文章
- 整理一下Entity Framework的查询 [转]
- Ruby 方法
- 向量时钟Vector Clock in Riak
- windows 下 scrapy的安装
- 在Nginx中搭建Nagios监控平台
- bootstrap 仿实例
- 转:Hprose for php(一)——快速入门
- VirtualBox镜像复制载入
- ThinkPHP第二十五天(自动完成、用户名密码PHP正则、移位或加密函数)
- 【Demo 0015】位置服务及地图
- CSS学习笔记3:选择器及优先级
- 2019.02.26 bzoj4311: 向量(线段树分治+凸包)
- Django--文件上传和下载,自测试可用
- Date与时间戳的相互转换(Java)
- Javascript 正则验证带 + 号的邮箱地址
- cocos2d-x 粒子动作 setTexture
- java中程序上线报错: tomcat中java.lang.OutOfMemoryError: PermGen space
- js 中常见的深拷贝的方法
- BZOJ5301:[CQOI2018]异或序列(莫队)
- asp.net中的cookie