首页 > 其他分享 >【笔记】分层图DJ

【笔记】分层图DJ

时间:2022-10-10 15:02:05浏览次数:88  
标签:DJ int make 笔记 vis 分层 dis

分层图的题都很麻烦地要在 dijkstra 外面套个循环,其实可以不用。

以经典模板 [JLOI2011] 飞行路线 为例,给 DJ 的优先队列里面的点加一维状态 \(k\),\(f(u,k)\) 可以免费转移到 \(f(v,k+1)\),也可以付费转移到 \(f(v,k)\)。

相当于 DJ 里面同时 \(k\) 层图都在跑,正确性显然(要是怀疑哪里有问题,套用普通 DJ 的证明就行)。复杂度 \(O(k(n+m\log m))\)。

模板题代码:

#include <bits/stdc++.h>

using namespace std;
const int N = 10005;
int n, m, K, S, T, dis[N][12], vis[N][12];
vector<pair<int, int>> g[N];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> K >> S >> T;
  for(int i = 1, a, b, c; i <= m; i++) {
    cin >> a >> b >> c;
    g[a].emplace_back(make_pair(b, c));
    g[b].emplace_back(make_pair(a, c));
  }
  
  memset(dis, 0x3f, sizeof dis);
  dis[S][0] = 0;
  q.push(make_tuple(0, S, 0));
  while(!q.empty()) {
    auto [d, u, k] = q.top();
    q.pop();
    if(vis[u][k]) continue;
    vis[u][k] = true;
    for(auto [v, w] : g[u]) {
      if(dis[v][k] > d + w) {
        dis[v][k] = d + w;
        q.push(make_tuple(dis[v][k], v, k));
      }
      if(k < K && dis[v][k + 1] > d) {
        dis[v][k + 1] = d;
        q.push(make_tuple(dis[v][k + 1], v, k + 1));
      }
    }
  }
  int ans = 1e9;
  for(int i = 0; i <= K; i++)
    ans = min(ans, dis[T][i]);
  cout << ans << '\n';
  
	return 0;
}

其实我今天刚学分层图,再来做道题吧。

P3119 [USACO15JAN]Grass Cownoisseur G:tajran 缩点之后就可以给权值取负把求最长路转化为求最短路,DJ 的时候分 \(f(u,0/1)\),\(f(u,0)\) 只能通过走逆向边的方法转移到 \(f(v,1)\) 即可。

标签:DJ,int,make,笔记,vis,分层,dis
From: https://www.cnblogs.com/huaruoji/p/16775727.html

相关文章

  • WEB学习笔记 html篇
    htmlHTML(HyperTextMarkupLanguage)是用来描述网页的一种语言。HTML不是一种编程语言,而是一种标记语言。学习HtML其实就是学习标签。快速入门新建文本文件,后缀名......
  • 上位笔记_03_ini配置文件读写(支持中文)
    下图所示内容根据不同设备会有不同内容,需要自定义,为了将该部分内容从代码中脱离采用ini配置的方式进行方便后续引用,将ini文件读写类放入工具类中集中存放。  在调节......
  • 37、linux下安装python3.6和django
    37.1、安装python:1、python介绍:python是一种面向对象的,解释型的计算机语言,它的特点是语法简介,优雅,简单易学。1989年诞生,Guido(龟叔)开发。编译型语言:代码在编译之后,编译成......
  • 221010嵌入式系统高级C语言编程_笔记
    C语言不检查数组越界和内存缓冲区越界编译器对局部变量有两种存储方式,对于简单数据类型的变量(比如int,char,short或者指针变量等)编译器会首先尽可能的采用CPU内部的通用寄存......
  • 49、django工程(cookie+session)
    49.1、介绍:1、cookie不属于http协议范围,由于http协议无法保持状态,但实际情况,我们却又需要“保持状态”,因此cookie就是在这样一个场景下诞生。cookie的工作原理是,由服务器产......
  • 44、djanjo工程(介绍)
    44.1、什么时web框架:1、框架,即framework,特指为解决一个开放性问题而设计的具有一定约束性的支撑结构,使用看框架可以帮助你快速开发特定的形同,简单的说,就是你用别人搭建好的......
  • 46、django工程(view)
    46.1、djangoview视图函数说明:1、http请求中产生两个核心对象:(1)http请求:HttpRequest对象。(2)http响应:HttpResponse对象。2、views函数是接收用户请求,处理业务逻辑的函数:46.......
  • 深入理解css 笔记(3)
    过去经常将网页的根元素字号设置为0.625em或者62.5%。这样是为了将全局的font-size改成10px。这样设计师希望字号14px时,只需要写成1.4rem就好了。还使用了相对单......
  • 基于分层自监督学习将视觉Transformer扩展到千兆像素图像
    公众号ID|ComputerVisionGzq​论文地址:https://arxiv.org/pdf/2206.02647.pdf计算机视觉研究院专栏作者:Edison_GVisionTransformers(ViT)及其多尺度和分层变体已成功地捕......
  • 尚硅谷-JavaWeb Day6 JavaEE三层架构及web分层结构
    JavaEE三层架构介绍分层的目的是为了解耦,解耦就是为了降低代码耦合度,方便项目后期的维护和升级; web层:com.xxx.web/servlet/controllerservice层:com.xxx.serv......