首页 > 其他分享 >AcWing 850. Dijkstra求最短路 II

AcWing 850. Dijkstra求最短路 II

时间:2023-08-09 22:35:16浏览次数:38  
标签:850 idx int 距离 II Dijkstra heap ver 号点

JWvFczgRNg.jpg

题目

给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。

请你求出 $1$ 号点到 $n$ 号点的最短距离,如果无法从 $1$ 号点走到 $n$ 号点,则输出 $−1$。

输入格式 第一行包含整数 $n$ 和 $m$。

接下来 $m$ 行每行包含三个整数 $x,y,z$,表示存在一条从点 $x$ 到点 $y$ 的有向边,边长为 $z$。

输出格式 输出一个整数,表示 $1$ 号点到 $n$ 号点的最短距离。

如果路径不存在,则输出 $−1$。

数据范围 $1≤n,m≤1.5×10^5$,图中涉及边长均不小于 $0$,且不超过 $10000$。 数据保证:如果最短路存在,则最短路的长度不超过 $10^9$。

输入样例:

3 3
1 2 2
2 3 1
1 3 4

输出样例:

3

思路

与朴素版本相比,存在以下区别:

  1. 通过堆来实现获取点 $i$ 的最近点,从 $O(n)$ 到 $O(1)$

其余步骤大致相同

代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int d[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    // 1. 初始化距离,点1距离为0,其余为正无穷
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    
    // 存pair是因为小根堆是根据距离来判断的,我们要获得距离最近的点
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});  // 距离在前
    
    // 循环操作堆顶元素
    while (heap.size())
    {
        // 2. 获取距离最近点t
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        
        // 3. 判断堆顶t对应的元素是否已经被确认过
        if (st[ver]) continue;
        st[ver] = true;
        
        // 4. 用点ver来更新所有出边端点,更新成功则入队
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] > d[ver] + w[i])
            {
                d[j] = d[ver] + w[i];
                heap.push({d[j], j});
            }
        }
    }
    
    if (d[n] == 0x3f3f3f3f) return -1;
    
    return d[n];
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    printf("%d", dijkstra());
    
    return 0;
}

标签:850,idx,int,距离,II,Dijkstra,heap,ver,号点
From: https://blog.51cto.com/u_16170343/7026466

相关文章

  • 关于硬件IIC卡死在各事件的解决方法
    1、关于硬件IIC卡死在EV5事件解决方法主机使用I2C_GenerateSTART()函数发送START条件后,主机必须等待事件5(启动条件已在I2C总线上正确释放),关于事件5,主要是对是否发送起始位(STAR1寄存器位0)、主从模式以及总线是忙还是空闲(STAR2寄存器位0、位1)进行判断,当这3位均为1,即已发送起始位、主......
  • Acwing 849. Dijkstra求最短路 I
    题目给定一个$n$个点$m$条边的有向图,图中可能存在重边和自环,所有边权均为正值。请你求出$1$号点到$n$号点的最短距离,如果无法从$1$号点走到$n$号点,则输出$−1$。输入格式第一行包含整数$n$和$m$。接下来$m$行每行包含三个整数$x,y,z$,表示存在一条从点$x$......
  • LeetCode 热题 100 之 240. 搜索二维矩阵 II
    题目编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例一输入:matrix=[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],target=5......
  • win10 iis - 开启iis且配置站点后,访问静态页面空白 - 解决
     勾选这三个即可 ......
  • 内存溢出后重启IIS后,附加到进程调试 ,找不到w3wp.exe进程。
    打开IIS,右键浏览一下。这个时候附加到进程调试里的选项就有了!本文来自博客园,作者:小二↑上酒,转载请注明原文链接:https://www.cnblogs.com/qh1688/p/7383925.html......
  • 剑指 Offer 32 - III. 从上到下打印二叉树 III(中等)
    题目:解法一:classSolution{public:voidtraversal(TreeNode*cur,vector<vector<int>>&result,intdepth){if(cur==nullptr)return;if(result.size()==depth)result.push_back(vector<int>());result[depth].pu......
  • Windows server 2003怎么安装iisWindows server 2003安装IIS教程
    Windows2008系统服务器安装IIS之前已经分享过了,和Windows2003完全不同,今天我将详细地和你分享Windowsserver2003卸载和安装IIS的步骤方法,希望可以帮助到你~1、首先进入服务器,确定下服务器是否有安装IIS,有安装IIS,需要重装的,可以先将IIS卸载。2、卸载比安装更简单些,点击开始——......
  • 洛谷 P8500 - [NOI2022] 冒泡排序
    显然将权值离散化是没有问题的,因为必然存在一组最优解,满足每个\(a_i\)都取自于某个\(V_i\),于是不管三七二十一先将\(V_i\)离散化了再说。考虑从部分分入手逐步分析这道题:特殊性质A:\(V_i=1\)相当于这个区间中的数必须是\(1\),先将这些数去掉不管,紧接着考虑\(V_i=0\)的......
  • [国家集训队] Tree II 题解报告
    [国家集训队]TreeII一道·真·板子·题就是练习LCT懒标记的题目除了翻转标记以外还要维护乘法标记和加法标记注意加法标记和乘法标记的维护!!!加法标记因为splay的区间大小不是固定的,所以我们要维护size,并且子树的sum要加上size乘上标记其他的就只用直接加上即可voidpusha......
  • Dijkstra最短路径算法及其优化
    Dijkstra最短路径算法及其优化图示过程可以参考图文详解Dijkstra最短路径算法(freecodecamp.org)直接给出Java版本的普通实现方式:/***最普通的实现形式,时间复杂度是O(n2),空间复杂度是O(n)*@paramweight*@paramstart*@return*/publicstaticint[]getDij......