首页 > 其他分享 >【CF1715E】Long Way Home

【CF1715E】Long Way Home

时间:2023-07-02 15:00:30浏览次数:41  
标签:val int mid CF1715E Way ls Home line dis

这个 \(k\) 非常小,所以我们考虑全部依次飞这 \(k\) 次行程。

这个飞来飞去是一个平方的形式,我们考虑优化这一形式。

首先我们知道从 \(u\) 飞到 \(v\) 后就可以这样做:

\[dis_u + (u -v)^2 \to dis_v \]

\[dis_u + u^2 + v^2 - 2uv \to dis_v \]

这里我们可以钦定 \(u < v\),然后斜率优化做两遍,但是感觉不如直接写李超树维护即可。

但是更新后的点可以在走一些路,然后就会更新到一些城市的答案,所以考虑先进行算完斜率优化,再跑一遍 dijkstra 即可。

时间复杂度 \(kn\log (n+ m)\)。

代码:

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ls u << 1
#define rs u << 1 | 1

const int N = 1e5 + 5, MOD = 998244353;

struct NODE {
	int u, w;
	bool operator < (const NODE & x) const {
		return w > x.w;
	} 
};

priority_queue <NODE> q;
vector <pair<int, int>> e[N];

struct line {
	int k, b;
	line (int k = 0, int b = 1e16) : k(k), b(b) {}	
	inline int val (int x) { return k * x + b; }
} ;

struct lichaotree {
	line t[N << 2];
	inline void clear (int u, int l, int r) {
		if (l == r || t[u].k == 0) return ;
		t[u].k = 0, t[u].b = 1e18; 
		int mid = (l + r) >> 1;
		clear(ls, l, mid), clear(rs, mid + 1, r);
	}
	inline void modify (int u, int l, int r, line x) {
		if (l == r) {
			if (x.val(l) < t[u].val(l)) t[u] = x; 
			return ;
		} int mid = (l + r) >> 1;
		if (x.val(mid) < t[u].val(mid)) swap(x, t[u]);
		if (x.val(l) < t[u].val(l)) modify(ls, l, mid, x);
		if (x.val(r) < t[u].val(r)) modify(rs, mid + 1, r, x);
	}
	inline int query (int u, int l, int r, int pos) {
		int res = t[u].val(pos), mid = (l + r) >> 1;
		if (l == r) return res;
		if (pos <= mid) return min(res, query(ls, l, mid, pos));
		else return min(res, query(rs, mid + 1, r, pos));
	}
} lct;

int n, m, k;
int dist[N];

inline void dijkstra () {
	for (int i = 1; i <= n; i ++) q.push({i, dist[i]});
	while (! q.empty()) {
		NODE t = q.top(); q.pop();
		int u = t.u, d = t.w;
		if (d != dist[u]) continue ;
		for (auto & [v, w] : e[u])
			if (dist[v] > d + w) dist[v] = d + w, q.push({v, dist[v]});
	}
}

signed main () {
	ios :: sync_with_stdio(0);
	cin >> n >> m >> k;
	for (int i = 1, u, v, w; i <= m; i ++) {
		cin >> u >> v >> w;
		e[u].emplace_back(v, w), e[v].emplace_back(u, w);
	}
	for (int i = 2; i <= n; i ++) dist[i] = 1e16;
	dijkstra();
	for (int i = 1; i <= k; i ++) {
		lct.clear(1, 1, n);
		for (int j = 1; j <= n; j ++)
			lct.modify(1, 1, n, line(-2 * j, j * j + dist[j]));
		for (int j = 1; j <= n; j ++)
			dist[j] = min(dist[j], lct.query(1, 1, n, j) + j * j);
		dijkstra();
	}
	for (int i = 1; i <= n; i ++) cout << dist[i] << " ";
	return 0;
}

标签:val,int,mid,CF1715E,Way,ls,Home,line,dis
From: https://www.cnblogs.com/Custlo/p/17520810.html

相关文章

  • Nginx 报错 504 Gateway Time-out 和无法上传大于1M文件的解决方法
    Nginx报错504GatewayTime-out的解决方法修改nginx.conf配置文件。keepalive_timeout600;fastcgi_connect_timeout600;fastcgi_send_timeout600;fastcgi_read_timeout600;proxy_connect_timeout600;proxy_send_timeout600;proxy_read_timeou......
  • 【SpringCloud】Gateway
    目录1.Gateway简介1.1Gateway工作流程1.2Gateway三大核心概念......
  • SpringGateway中鉴权及添加参数
    SpringGateway中对请求头中的Token进行验证,并获取到相应的账号信息,通过添加参数的方式传递到后续的服务中packagecn.lixuelong.gateway.config;importjava.net.URI;importjava.nio.charset.StandardCharsets;importorg.slf4j.Logger;importorg.slf4j.LoggerFactory;i......
  • 设备通过海康ehome接入到EasyCVR后,通道数量显示不全是什么原因?
    EasyCVR可拓展性强、视频能力灵活、部署轻快,可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等,以及厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等,能对外分发RTSP、RTMP、FLV、HLS、WebRTC等格式的视频流。有用户反馈,现场设备通过海康ehome协议接入到EasyCVR中,虽然显......
  • mac 下使用 brew 安装包报错 error: Cannot install under Rosetta 2 in ARM default
    mac下使用brew安装包报错error:CannotinstallunderRosetta2inARMdefaultprefix(/opt/homebrew)!TorerununderARMuse:arch-arm64brewinstall...Toinstallunderx86_64,installHomebrewinto/usr/local. 解决:arch-arm64brewinstallxxx ......
  • Spring Cloud Gateway编码实现任意地址跳转
    欢迎访问我的GitHub这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos本篇概览作为《SpringCloudGateway实战》系列的第十四篇,本文会继续发掘SpringCloudGateway的潜力,通过编码体验操控网关的乐趣,开发出一个实用的功能:让SpringCloudGa......
  • Linux将home磁盘空间分给root_随笔记
    ==========================================将home空间配给roottarcvf/home.tar/home#备份家目录fuser-km/home#终止家目录所有进程umount/home#卸载家目录lvremove/dev/mapper/......
  • gateway基本配置
    gateway基本配置1、gateway简介路由转发+执行过滤器链。网关,旨在为微服务架构提供一种简单有效的统一的API路由管理方式。同时,基于Filter链的方式提供了网关的基本功能,比如:鉴权、流量控制、熔断、路径重写、黑白名单、日志监控等。基本功能如下:统一入口:暴露出网关地址,作为......
  • 时速云使用 Higress 替换 Ngnix Ingress + Spring Cloud Gateway 的生产实践
    作者:王金山,北京云思畅想科技有限公司技术部微服务架构师,负责公司API网关和服务网格等研发工作时速云介绍时速云成立于2014年10月,致力于通过云原生技术帮助企业实现数字化转型,拥有云原生应用平台TCAP和云原生数据平台KubeData两大核心产品体系,产品包含云原生DevOps、容器......
  • 微服务 – Spring Cloud – Gateway
    微服务–SpringCloud–GatewayApi网关(ApiGateway)微服务可能分布在不同的主机上,这样有许多缺点:前端需要硬编码调用不同地址的微服务很麻烦;存在跨域访问的问题;微服务地址直接暴露是不安全的。还有所以需要为前端提供一个统一的访问入口。Gateway就是用于解决以上问题的框......