HDU1874畅通工程续 dijkstrafloyd

2024-08-27 23:32

本文主要是介绍HDU1874畅通工程续 dijkstrafloyd,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

畅通工程续

http://acm.hdu.edu.cn/showproblem.php?pid=1874

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15713    Accepted Submission(s): 5371

Problem Description
某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。
Input
本题目包含多组数据,请处理到文件结束。 每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000),分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0~N-1编号。 接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。 再接下一行有两个整数S,T(0<=S,T<N),分别代表起点和终点。
Output
对于每组数据,请在一行里输出最短需要行走的距离。如果不存在从S到T的路线,就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
dijsktra:
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define inf 0x3f3f3f3f
int n,m,a,b,x,s,t;
int map[205][205];//邻接矩阵存图;
bool vis[205];//标记是否被访问过
int dis[205];//存每个点距源点的距离
void dijkstra(int s)
{for(int i=0;i<n;i++){dis[i]=map[s][i];vis[i]=false;}dis[s]=0;vis[s]=true;int pos,min;for(int i=1;i<n;i++){min=inf;for(int j=0;j<n;j++){if(!vis[j]&&dis[j]<min){min=dis[j];pos=j;}}vis[pos]=true;for(int j=0;j<n;j++){if(!vis[j]&&dis[j]>dis[pos]+map[pos][j])dis[j]=dis[pos]+map[pos][j];}}
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)for(int j=0;j<n;j++){map[i][j]=map[j][i]=inf;}for(int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&x);if(map[a][b]>x)          //如果有重边!!!!map[a][b]=map[b][a]=x;}scanf("%d%d",&s,&t);dijkstra(s);if(dis[t]==inf)printf("-1\n");elseprintf("%d\n",dis[t]);}return 0;
}

floyd:
#include<stdio.h>
#include<iostream>
using namespace std;
#define inf 0x3f3f3f3f
int n,m,a,b,x,s,t;
int map[205][205];
void floyd()
{for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(map[i][k]+map[k][j]<map[i][j])map[i][j]=map[i][k]+map[k][j];}
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)for(int j=0;j<n;j++)map[i][j]=(i==j?0:inf);for(int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&x);if(map[a][b]>x)map[a][b]=map[b][a]=x;}scanf("%d%d",&s,&t);floyd();if(map[s][t]==inf)printf("-1\n");else printf("%d\n",map[s][t]);}return 0;
}


这篇关于HDU1874畅通工程续 dijkstrafloyd的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1113096

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

Jenkins构建Maven聚合工程,指定构建子模块

一、设置单独编译构建子模块 配置: 1、Root POM指向父pom.xml 2、Goals and options指定构建模块的参数: mvn -pl project1/project1-son -am clean package 单独构建project1-son项目以及它所依赖的其它项目。 说明: mvn clean package -pl 父级模块名/子模块名 -am参数

二、Maven工程的创建--JavaSEJavaEE

1、idea创建Maven JavaSE工程:  2、idea创建Maven JavaEE工程:   (1)手动创建 (2)插件方式创建 在idea里安装插件JBLJavaToWeb; 选择需要生成的项目文件后,右击: 项目的webapp文件夹出现小蓝点,代表成功。

三、Maven工程的构建

首先,创建和构建是两个概念。 构建是指将源代码、依赖库和资源文件等转换为可执行或可部署的应用程序的过程。 在这个过程中包括编译源代码、链接依赖库、打包和部署等多个步骤。 项目构建是软件开发过程中至关重要的一部分,它能够大大提高软件开发效率,使得开发人员更加专注于应用程序的开发和维护,而不必关心应用程序的构建细节。 同时,项目构建还能将多人写的代码聚合,并能够自动化项目的构建和部署,

我在高职教STM32——准备HAL库工程模板(1)

新学期开学在即,又要给学生上 STM32 嵌入式课程了。这课上了多年了,一直用的都是标准库来开发,已经驾轻就熟了。人就是这样,有了自己熟悉的舒适圈,就很难做出改变,老师上课也是如此,排斥新课和不熟悉的内容。显然,STM32 的开发,HAL 库已是主流,自己其实也在使用,只不过更换库就意味着教学内容有很大变化,自己也就迟迟没有迈出调整这一步。现在,是时候做出变化了,笔者计划保持教学项

java工程的导入jar包

由于现在学习java web,java工程导入jar包都忘记了。 在此想记录一下:工程项目名:右击 -- Build Path --add External Archives 点击会弹出一个框 ,选择你要导入的jar路径就可以了。

【MyBatis学习14】MyBatis的逆向工程生成代码

1. 什么是逆向工程 mybatis的一个主要的特点就是需要程序员自己编写sql,那么如果表太多的话,难免会很麻烦,所以mybatis官方提供了一个逆向工程,可以针对单表自动生成mybatis执行所需要的代码(包括mapper.xml、mapper.java、po..)。一般在开发中,常用的逆向工程方式是通过数据库的表生成代码。 2. 使用逆向工程 使用mybatis的逆向工程,需要导入逆向

maven-聚合工程

聚合工程: 聚合工程里可以分为顶级项目(顶级工程、父工程)与子工程,这两者的关系其实就是父子继承的关系,子工程在maven里称之为模块(module),模块之间是平级,是可以相互依赖的。子模块可以使用顶级工程里所有的资源(依赖),子模块之间如果要使用资源,必须构建依赖(构建关系)一个顶级工程是可以由多个不同的子工程共同组合而成。

图特征工程实践指南:从节点中心性到全局拓扑的多尺度特征提取

图结构在多个领域中扮演着重要角色,它能有效地模拟实体间的连接关系,通过从图中提取有意义的特征,可以获得宝贵的信息提升机器学习算法的性能。 本文将介绍如何利用NetworkX在不同层面(节点、边和整体图)提取重要的图特征。 本文将以NetworkX库中提供的Zachary网络作为示例。这个广为人知的数据集代表了一个大学空手道俱乐部的社交网络,是理解图特征提取的理想起点。 我们先定义一些辅助函数

Springboot工程配置https访问

背景 因为前端工程使用nginx配置了https访问,在https直接请求我们Springboot后端的http接口会报错。那么我们就需要配置使得我们后端的springboot服务支持https访问。 证书生成 在配置springboot工程https之前,我们需要生成自签名证书以及Spring Boot通常使用的PKCS#12格式的密钥库。 生成自签名证书 openssl req -x