P3371 【模板】单源最短路径（弱化版）_p3371单源最短路径-程序员宅基地

技术标签：算法 c语言图论

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。

输出格式

输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31−1。

输入输出样例

输入 #1复制

输出 #1复制

0 2 4 3

说明/提示

【数据范围】
对于 20%20% 的数据：1≤n≤5，1≤m≤15；
对于 40%40% 的数据：1≤n≤100，1≤m≤10^4；
对于 70%70% 的数据：1≤n≤1000,1≤m≤10^5；
对于 100%100% 的数据：1≤n≤10^4，1≤m≤5×10^5，1≤u,v≤n，w≥0，保证数据随机。

Update 2022/07/29：两个点之间可能有多条边，敬请注意。

对于真正 100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

图片1到3和1到4的文字位置调换

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 2147483647
int first[10001],next[500005],u[500005],v[500005],w[500005],dis[10005],book[10005];
int main()
{
	int n,m,s,x;
	scanf("%d%d%d",&n,&m,&s);
	memset(first,-1,sizeof(first));//初始化数组；
	for(int i=1;i<=n;i++)
	dis[i]=max;
	book[s]=1;
	dis[s]=0;
	for(int i=1;i<=m;i++)//建立邻接表；
	{
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
		next[i]=first[u[i]];
		first[u[i]]=i;
	}
	x=first[s];
	while(x!=-1)//遍历邻接表；
	{
		if(dis[v[x]]>w[x])
		dis[v[x]]=w[x];
		x=next[x];
	}
	for(int i=1;i<n;i++)
	{
		int k=0;
		int min=max;
		for(int j=1;j<=n;j++)
		{
			if(book[j]==0&&dis[j]<min)
			{
				min=dis[j];
			    k=j;
			}
		}
		book[k]=1;
		x=first[k];
	    while(x!=-1)
	    {
		    if(dis[v[x]]>dis[k]+w[x])
		    dis[v[x]]=dis[k]+w[x];
		    x=next[x];
	    }
	}
	for(int i=1;i<=n;i++)
	printf("%d ",dis[i]);
	return 0;
}

本文链接：https://blog.csdn.net/weixin_74019136/article/details/128910238

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

获取大于等于一个整数的最小2次幂算法（HashMap#tableSizeFor）_整数最小的2的几次方-程序员宅基地

文章浏览阅读2w次，点赞51次，收藏33次。一、需求给定一个整数，返回大于等于该整数的最小2次幂（2的乘方）。例：输入输出 -1 1 1 1 3 4 9 16 15 16二、分析当遇到这个需求的时候，我们可能会很容易想到一个"笨"办法：..._整数最小的2的几次方

Linux 中 ss 命令的使用实例_ss@,,x,, 0-程序员宅基地

文章浏览阅读865次。选项，以防止命令将 IP 地址解析为主机名。如果只想在命令的输出中显示 unix套接字连接，可以使用。不带任何选项，用来显示已建立连接的所有套接字的列表。如果只想在命令的输出中显示 tcp 连接，可以使用。如果只想在命令的输出中显示 udp 连接，可以使用。如果不想将ip地址解析为主机名称，可以使用。如果要取消命令输出中的标题行，可以使用。如果只想显示被侦听的套接字，可以使用。如果只想显示ipv4侦听的，可以使用。如果只想显示ipv6侦听的，可以使用。_ss@,,x,, 0

conda activate qiuqiu出现不存在activate_commandnotfounderror: 'activate-程序员宅基地

文章浏览阅读568次。CommandNotFoundError: 'activate'_commandnotfounderror: 'activate

Kafka 实战 - Windows10安装Kafka_win10安装部署kafka-程序员宅基地

文章浏览阅读426次，点赞10次，收藏19次。完成以上步骤后，您已在 Windows 10 上成功安装并验证了 Apache Kafka。在生产环境中，通常会将 Kafka 与外部 ZooKeeper 集群配合使用，并考虑配置安全、监控、持久化存储等高级特性。在生产者窗口中输入一些文本消息，然后按 Enter 发送。ZooKeeper 会在新窗口中运行。在另一个命令提示符窗口中，同样切换到 Kafka 的。Kafka 服务器将在新窗口中运行。在新的命令提示符窗口中，切换到 Kafka 的。，应显示已安装的 Java 版本信息。_win10安装部署kafka

【愚公系列】2023年12月 WEBGL专题-缓冲区对象_js 缓冲数据 new float32array-程序员宅基地

文章浏览阅读1.4w次。缓冲区对象（Buffer Object）是在OpenGL中用于存储和管理数据的一种机制。缓冲区对象可以存储各种类型的数据，例如顶点、纹理坐标、颜色等。在渲染过程中，缓冲区对象中存储的数据可以被复制到渲染管线的不同阶段中，例如顶点着色器、几何着色器和片段着色器等，以完成渲染操作。相比传统的CPU访问内存，缓冲区对象的数据存储和管理更加高效，能够提高OpenGL应用的性能表现。_js 缓冲数据 new float32array

四、数学建模之图与网络模型_图论与网络优化数学建模-程序员宅基地

文章浏览阅读912次。（1）图（Graph）：图是数学和计算机科学中的一个抽象概念，它由一组节点（顶点）和连接这些节点的边组成。图可以是有向的（有方向的，边有箭头表示方向）或无向的（没有方向的，边没有箭头表示方向）。图用于表示各种关系，如社交网络、电路、地图、组织结构等。（2）网络（Network）：网络是一个更广泛的概念，可以包括各种不同类型的连接元素，不仅仅是图中的节点和边。网络可以包括节点、边、连接线、路由器、服务器、通信协议等多种组成部分。网络的概念在各个领域都有应用，包括计算机网络、社交网络、电力网络、交通网络等。_图论与网络优化数学建模

随便推点

android 加载布局状态封装_adnroid加载数据转圈封装全屏转圈封装-程序员宅基地

文章浏览阅读1.5k次。我们经常会碰见正在加载中，加载出错， “暂无商品”等一系列的相似的布局，因为我们有很多请求网络数据的页面，我们不可能每一个页面都写几个“正在加载中”等布局吧，这时候将这些状态的布局封装在一起就很有必要了。我们可以将这些封装为一个自定布局，然后每次操作该自定义类的方法就行了。首先一般来说，从服务器拉去数据之前都是“正在加载”页面，加载成功之后“正在加载”页面消失，展示数据；如果加载失败，就展示_adnroid加载数据转圈封装全屏转圈封装

阿里云服务器（Alibaba Cloud Linux 3）安装部署Mysql8-程序员宅基地

文章浏览阅读1.6k次，点赞23次，收藏29次。PS: 如果执行sudo grep 'temporary password' /var/log/mysqld.log 后没有报错，也没有任何结果显示，说明默认密码为空，可以直接进行下一步（后面设置密码时直接填写新密码就行）。3.（可选）当操作系统为Alibaba Cloud Linux 3时，执行如下命令，安装MySQL所需的库文件。下面示例中，将创建新的MySQL账号，用于远程访问MySQL。2.依次运行以下命令，创建远程登录MySQL的账号，并允许远程主机使用该账号访问MySQL。_alibaba cloud linux 3