P4779 【模板】单源最短路径(标准版)
admin
2024-05-23 10:50:28
0

# 【模板】单源最短路径(标准版)

## 题目背景

2018 年 7 月 19 日,某位同学在 [NOI Day 1 T1 归程](https://www.luogu.org/problemnew/show/P4768) 一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢?

$100 \rightarrow 60$;

$\text{Ag} \rightarrow \text{Cu}$;

最终,他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

## 题目描述

给定一个 $n$ 个点,$m$ 条有向边的带非负权图,请你计算从 $s$ 出发,到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

## 输入格式

第一行为三个正整数 $n, m, s$。
第二行起 $m$ 行,每行三个非负整数 $u_i, v_i, w_i$,表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

## 输出格式

输出一行 $n$ 个空格分隔的非负整数,表示 $s$ 到每个点的距离。

## 样例 #1

### 样例输入 #1

```
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
```

### 样例输出 #1

```
0 2 4 3
```

## 提示

样例解释请参考 [数据随机的模板题](https://www.luogu.org/problemnew/show/P3371)。

$1 \leq n \leq 10^5$;

$1 \leq m \leq 2\times 10^5$;

$s = 1$;

$1 \leq u_i, v_i\leq n$;

$0 \leq w_i \leq 10 ^ 9$,

$0 \leq \sum w_i \leq 10 ^ 9$。

本题数据可能会持续更新,但不会重测,望周知。

2018.09.04 数据更新 from @zzq

1.这个问题用dijkstra算法即可,要使用堆优化的dijkstra算法,否则会时间超限。

2.刚开始我是想自己手写一个堆,模拟优先队列,然而修修改改还是只是AC了俩个点 ,没办法去学了C++里面的STL里的优先队列。

3.继而就简单多了(代码少了将近一大半)

4.堆优化的dijkstra算法也是非常简单,核心思想是一样的,先松弛,再找最近的那一个点,继续松弛循环下去。用堆来实现就是把新更新的距离权值入队,然后在优先队列里面会自动在首元素是最小值了。我们只需要判断堆顶元素是否访问过即可,如果访问过了,就弹出堆顶元素,继续找就可以。

    while( !q.empty() )//如果队列不为空,就需要继续访问{tmp = q.top();//访问堆顶元素q.pop();//弹出队头x = tmp.pos, w = tmp.w;if( book[x] )continue;//如果该点已经纳入最短路径,需要跳过book[x] = 1;//从该点开始松弛for(i = head[x]; i; i = e[i].next )//链式前向星{y = e[i].to;if( dis[y] > dis[x] + e[i].w ){dis[y] = dis[x] + e[i].w;if( !book[y] ){q.push( ( node ){dis[y], y} );//插入元素并且重新排序}}}}

完整C++代码如下:

#include
#include
#include
#includeusing namespace std;const int N = 100010, M = 500010;
const int INF=1000000000;
struct edges
{int to;int w;int next;
}e[M];
int head[N], dis[N];
bool book[N];
int n, m, s;
struct node
{int w;int pos;bool operator <( const node &x )const{return x.w  q;//建立堆
void dijk()
{int i,y,x,w;node tmp;dis[s] = 0;q.push( ( node ){0, s} );//放入该节点,也就是入队while( !q.empty() )//如果队列不为空,就需要继续访问{tmp = q.top();//访问堆顶元素q.pop();//弹出队头x = tmp.pos, w = tmp.w;if( book[x] )continue;//如果该点已经纳入最短路径,需要跳过book[x] = 1;//从该点开始松弛for(i = head[x]; i; i = e[i].next )//链式前向星{y = e[i].to;if( dis[y] > dis[x] + e[i].w ){dis[y] = dis[x] + e[i].w;if( !book[y] ){q.push( ( node ){dis[y], y} );//插入元素并且重新排序}}}}for( i = 1; i <= n; i++ )printf( "%d ", dis[i] );
}
int main()
{int i,u,v,w;scanf( "%d%d%d", &n, &m, &s );for(i = 1; i <= n; i++) dis[i] =INF;for(i = 1; i <= m; i++){scanf( "%d%d%d", &u, &v, &w );e[i].to=v;e[i].w=w;e[i].next=head[u];head[u]=i;}dijk();return 0;
}

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作: 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统(六):学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤: 在Student.cpp的...
JAVA多线程知识整理 Java多线程基础 线程的创建和启动 继承Thread类来创建并启动 自定义Thread类的子类&#...
【洛谷 P1090】[NOIP... [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G ...
国民技术LPUART介绍 低功耗通用异步接收器(LPUART) 简介 低功耗通用异步收发器...
城乡供水一体化平台-助力乡村振... 城乡供水一体化管理系统建设方案 城乡供水一体化管理系统是运用云计算、大数据等信息化手段࿰...
程序的循环结构和random库...   第三个参数就是步长     引入文件时记得指明字符格式,否则读入不了 ...
中国版ChatGPT在哪些方面... 目录 一、中国巨大的市场需求 二、中国企业加速创新 三、中国的人工智能发展 四、企业愿景的推进 五、...
报名开启 | 共赴一场 Flu... 2023 年 1 月 25 日,Flutter Forward 大会在肯尼亚首都内罗毕...
汇编00-MASM 和 Vis... Qt源码解析 索引 汇编逆向--- MASM 和 Visual Studio入门 前提知识ÿ...
【简陋Web应用3】实现人脸比... 文章目录🍉 前情提要🌷 效果演示🥝 实现过程1. u...
前缀和与对数器与二分法 1. 前缀和 假设有一个数组,我们想大量频繁的去访问L到R这个区间的和,...
windows安装JDK步骤 一、 下载JDK安装包 下载地址:https://www.oracle.com/jav...
分治法实现合并排序(归并排序)... 🎊【数据结构与算法】专题正在持续更新中,各种数据结构的创建原理与运用✨...
在linux上安装配置node... 目录前言1,关于nodejs2,配置环境变量3,总结 前言...
Linux学习之端口、网络协议... 端口:设备与外界通讯交流的出口 网络协议:   网络协议是指计算机通信网...
Linux内核进程管理并发同步... 并发同步并发 是指在某一时间段内能够处理多个任务的能力,而 并行 是指同一时间能够处理...
opencv学习-HOG LO... 目录1. HOG(Histogram of Oriented Gradients,方向梯度直方图)1...
EEG微状态的功能意义 导读大脑的瞬时全局功能状态反映在其电场结构上。聚类分析方法一致地提取了四种头表面脑电场结构ÿ...
【Unity 手写PBR】Bu... 写在前面 前期积累: GAMES101作业7提高-实现微表面模型你需要了解的知识 【技...