首页 > 其他分享 >DIjkstra进阶模板 路径记录 按权重(结点数最小等)记录

DIjkstra进阶模板 路径记录 按权重(结点数最小等)记录

时间:2024-03-31 13:13:02浏览次数:22  
标签:node 进阶 val 记录 int DIjkstra que path dis

struct DIJ {
    using i64 = long long;
    using PII = pair<i64, i64>;
    vector<i64> dis, path, node;
    vector<vector<array<int, 3>>> G;
    int n;

    DIJ() {}
    DIJ(int n): n(n) {
        node.resize(n + 1, 1);
        dis.assign(n + 1, 1e18);
        G.resize(n + 1);
        path.resize(n + 1, -1);
    }
	//val为权重值,要求最短路径结点数最小时即为1
    void add(int u, int v, int w, int val) {
        G[u].push_back({v, w, val});
    }

    void dijkstra(int s) {
        priority_queue<PII> que;
        dis[s] = 0;
        que.push({0, s});
        while (!que.empty()) {
            auto p = que.top();
            que.pop();
            int u = p.second;
            if (dis[u] < p.first) continue;
            for (auto [v, w, val] : G[u]) {
                if (dis[v] > dis[u] + w) {
                    node[v] = node[u] + val;
                    dis[v] = dis[u] + w;
                    que.push({ -dis[v], v});
                    path[v] = u;
                } else if (dis[v] == dis[u] + w) {
                    if (node[v] > node[u] + val) {
                        node[v] = node[u] + val;
                        path[v] = u;
                    }
                }
            }
        }
    }
};

标签:node,进阶,val,记录,int,DIjkstra,que,path,dis
From: https://www.cnblogs.com/Kescholar/p/18106617

相关文章

  • Pintia 天梯地图 dijkstra进阶
    7-14天梯地图-SMU2024spring天梯赛3(补题)(pintia.cn)dijkstra进阶做法,包含路径记录,以及按权重统计路径条件等;不过最开始我一直将优先队列开的最大堆,但是一直过不了自己的例子,后来改成最小堆并且路径值改成负数存进去就对了,再后来我发现改成最大堆也可以,不过要把......
  • Python之Opencv进阶教程(2):统计图片灰度级别的像素数量
    1、什么是灰度像素数量在OpenCV中,可以使用**cv2.calcHist()**函数来计算图像的直方图。直方图是一种图形统计表,用于表示图像中每个灰度级别(或颜色通道)的像素数量或密度分布。以下是一个示例代码,演示了如何使用OpenCV计算和绘制图像的直方图:2、代码importcv2ascvimpor......
  • Python之Opencv进阶教程(1):图片模糊
    1、Opencv提供了多种模糊图片的方法加载原始未经模糊处理的图片importcv2ascvimg=cv.imread('../Resources/Photos/girl.jpg')cv.imshow('girl',img)1.1平均值关键代码#Averaging平均值a......
  • 记录一次在设计服务层和仓储层报错
    1、首先,使用SqlSugar.IOC连接SugarIocServices.AddSqlSugar(newIocConfig(){ConnectionString=GetConnectionObject(),DbType=IocDbType.SqlServer,IsAutoCloseConnection=true});2、在仓储层获取DB实例publicclassBase......
  • 【图论】3.30学习记录 k短路(A*算法)
    从最短路说起的k短路3.26看了最短路和次短路。我们发现次短路实际上就是把最短路给破坏掉然后跑最短路...那我想...是不是破坏(k-1)次就能得到k短路呢,很显然是的,但是复杂度比较高,(因为一次dij是O(nlogn)级别的,次短路的话最坏要跑m次当最短路有m条边的时候)那么k比较大的时候就......
  • Blazor学习记录_8.CSS隔离和代码隔离_异常处理_流式渲染
    19.CSS隔离和代码隔离19.1代码隔离使用C#partial关键字,创建一个与razor文件同名,扩展名加.CS的C#类文件,然后把razor文件中的@code中的代码迁移至cs文件中。注意命名空间、泛形参数声明、依赖注入的迁移19.2CSS隔离如同前面代码隔离文件一样,我们创建一个组件样式文......
  • react + electron 应用在线更新功能记录
    这个东西很多人都可能用electron-update这个玩意,但是我用了,发现总是更新不了,于是放弃,使用electron自带功能  主进程main.js中引入 const{autoUpdater}=require('electron-updater'); 以下为主要代码,也是放在main.js  autoUpdater.autoDownload=false......
  • RSA进阶(一)
    本篇为RSA进阶篇,继RSA入门[RSA3]P1(扩展欧几里得)题目fromCrypto.Util.numberimport*flag=b'******'m1=bytes_to_long(flag[:len(flag)//2])m2=bytes_to_long(flag[len(flag)//2:])assert18608629446895353521310408885845687520013234781800558*m1-142588104721......
  • 4、Pico Robot 传感器进阶课程
    4.1光敏传感器一、学习目标1.学习树莓派Pico主板和小车扩展板的光敏传感器、OLED结合进行实验。2.了解光敏传感器的使用。二、硬件使用本次课程使用PICO主板以及小车扩展板的光敏传感器、OLED,运行之前请把跳线帽接到Light排针。光敏电阻是用硫化镉或硒化镉等半导体材料......
  • FLASK学习记录-sqlite3基本操作
    sqltie3是内置模块,数据库操作,以及表的增删改查参考https://www.runoob.com/sqlite/sqlite-python.html实例创建数据库$sqlite3test.dbSQLiteversion3.34.12021-01-2014:10:07Enter".help"forusagehints.sqlite>.databasesmain:/usr/dog/flask_web/flask-test2......