浙大数据结构第七周之07-图6 旅游规划
题目详情:
有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。
输入格式:
输入说明:输入数据的第1行给出4个正整数N、M、S、D,其中N(2≤N≤500)是城市的个数,顺便假设城市的编号为0~(N−1);M是高速公路的条数;S是出发地的城市编号;D是目的地的城市编号。随后的M行中,每行给出一条高速公路的信息,分别是:城市1、城市2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。
输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出样例:
3 40
主要思路:
就是Dijkstra的变形
代码实现:
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE_NUMS 505
#define NONE -1
#define INF 100000
#define TRUE 1
#define FALSE 0
typedef int bool;
typedef struct MatrixGraphNode MatrixGraphNode;
typedef MatrixGraphNode* MGraph;
struct MatrixGraphNode {int VertexNums, EdgeNums;int Distance[MAX_NODE_NUMS][MAX_NODE_NUMS];int Fare[MAX_NODE_NUMS][MAX_NODE_NUMS];
};
MGraph CreateEmptyGraph(int vertexNums, int edgeNums) {MGraph graph = (MGraph)malloc(sizeof(MatrixGraphNode));graph->VertexNums = vertexNums;graph->EdgeNums = edgeNums;for(int i = 0; i < vertexNums; i++) {for(int j = 0; j < vertexNums; j++) {if(i == j) {graph->Distance[i][i] = 0;graph->Fare[i][i] = 0;}else {graph->Distance[i][j] = INF;graph->Fare[i][j] = INF;}}}return graph;
}
void InsertEdge(int start, int end, int distance, int fare, MGraph graph) {graph->Distance[start][end] = distance; graph->Distance[end][start] = distance;graph->Fare[start][end] = fare; graph->Fare[end][start] = fare;return;
}
MGraph BuildGraph(int vertexNums, int edgeNums) {MGraph graph = CreateEmptyGraph(vertexNums, edgeNums);int start, end, distance, fare;for(int i = 0; i < edgeNums; i++) {scanf("%d %d %d %d", &start, &end, &distance, &fare);InsertEdge(start, end, distance, fare, graph);}return graph;
}
int FindNearest(MGraph graph, int vis[], int start) {/*先找距离最近,距离同样近找最省钱*/int ret = NONE;int minDis = INF;int minFare = INF;for(int i = 0; i < graph->VertexNums; i++) {if(i != start && vis[i] == FALSE) {if(graph->Distance[start][i] < minDis) {ret = i;minDis = graph->Distance[start][i];minFare = graph->Fare[start][i];}else if(graph->Distance[start][i] == minDis) {if(graph->Fare[start][i] < graph->Fare[start][ret]) {ret = i;minDis = graph->Distance[start][i];minFare = graph->Fare[start][i];}}}}return ret;
}
void Dijksta(MGraph graph, int start, int end) {int path[MAX_NODE_NUMS];int vis[MAX_NODE_NUMS];int dis[MAX_NODE_NUMS];int fare[MAX_NODE_NUMS];/*初始化*/for(int i = 0; i < graph->VertexNums; i++) {vis[i] = FALSE;if(i != start) {if(graph->Distance[start][i] < INF) {path[i] = start;dis[i] = graph->Distance[start][i];fare[i] = graph->Fare[start][i];}else {path[i] = NONE;dis[i] = INF;fare[i] = INF;}}}path[start] = NONE;dis[start] = 0;fare[start] = 0;while(TRUE) {int nearest = FindNearest(graph, vis, start);if(nearest == NONE) {break;}vis[nearest] = TRUE;for(int i = 0; i < graph->VertexNums; i++) {if(i != nearest && vis[i] == FALSE && graph->Distance[nearest][i] < INF) {if(graph->Distance[nearest][i] < 0) {return;}else if(dis[nearest] + graph->Distance[nearest][i] < dis[i]) {path[i] = nearest;dis[i] = dis[nearest] + graph->Distance[nearest][i];fare[i] = fare[nearest] + graph->Fare[nearest][i];}else if(dis[nearest] + graph->Distance[nearest][i] == dis[i]) {if(fare[nearest] + graph->Fare[nearest][i] < fare[i]) {path[i] = nearest;fare[i] = fare[nearest] + graph->Fare[nearest][i];}}}} }printf("%d %d", dis[end], fare[end]);
}
int main() {int vertexNums, edgeNums, startPoint, endPoint;scanf("%d %d %d %d", &vertexNums, &edgeNums, &startPoint, &endPoint);MGraph graph = BuildGraph(vertexNums, edgeNums);Dijksta(graph, startPoint, endPoint);free(graph);return 0;
}
相关文章:
浙大数据结构第七周之07-图6 旅游规划
题目详情: 有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的…...

RocketMQ双主双从同步集群部署
🎈 作者:互联网-小啊宇 🎈 简介: CSDN 运维领域创作者、阿里云专家博主。目前从事 Kubernetes运维相关工作,擅长Linux系统运维、开源监控软件维护、Kubernetes容器技术、CI/CD持续集成、自动化运维、开源软件部署维护…...

分类预测 | MATLAB实现EVO-CNN多输入分类预测
分类预测 | MATLAB实现EVO-CNN多输入分类预测 目录 分类预测 | MATLAB实现EVO-CNN多输入分类预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.MATLAB实现EVO-CNN多输入分类预测 2.代码说明:量谷优化卷积神经网络的数据分类预测:要求于Matlab …...

DAY04_SpringMVC—SpringMVC简介PostMan和ApiFox工具使用SpringMVC请求与响应REST风格
目录 一 SpringMVC简介1 SpringMVC概述问题导入1.1 SpringMVC概述 2 入门案例问题导入2.0 回顾Servlet技术开发web程序流程2.1 使用SpringMVC技术开发web程序流程2.2 代码实现【第一步】创建web工程(Maven结构)【第二步】设置tomcat服务器,加…...

phpstorm配置ftp同步文件到服务器
这里的默认快捷键 不是 CtrlS ;需要设置快捷键,这里原来是save all操作时上传文件到服务器; ** 设置好快捷键后按 CtrlS就会同步文件(添加删除文件后保存,服务器也会同步) ** 搜索出save all 后…...
前端jd要求:了解一门后端开发语言优先 解决方案之Node.js
前端jd要求:了解一门后端开发语言优先 解决方案之Node.js 前言常见的后端开发语言一、什么是 Node.js二、学习 Node.js 的前置知识三、学习 Node.js 的步骤1、Node.js 的安装2、Node.js 的基本语法和 API模块导入和导出文件读写操作HTTP 服务器命令行参数 3、Node.j…...
什么是ServiceMesh(Istio一)
现在最火的后端架构无疑是微服务了,微服务将之前的单体应用拆分成了许多独立的服务应用,每个微服务都是独立的,好处自然很多,但是随着应用的越来越大,微服务暴露出来的问题也就随之而来了,微服务越来越多&a…...

【腾讯云 Cloud Studio 实战训练营】Hexo 框架 Butterfly 主题搭建个人博客
什么是Cloud Studio Cloud Studio 是基于浏览器的集成式开发环境(IDE),为开发者提供了一个永不间断的云端工作站。用户在使用 Cloud Studio 时无需安装,随时随地打开浏览器就能在线编程。 Hexo 博客成品展示 本人博客如下&…...

搭建Excel服务器
1、下载Excel服务器 下载地址 2、解压文件 3、打开服务器 4、服务器运行信息 5、连接测试 打开客户端 6、登录到服务器 默认账号 密码 admin 3 修改文件保存路径(服务器端点击配置) 7、客户端整体界面 8、配置权限 9、设计模板 10、其他用户登录就可以填写信息 11、用户&#…...
渗透测试成功的8个关键
渗透测试 (penetration test)并没有一个标准的定义,国外一些安全组织达成共识的通用说法是:渗透测试是通过模拟恶意黑客的攻击方法,来评估计算机网络系统安全的一种评估方法。这个过程包括对系统的任何弱点、技术缺陷或漏洞的主动分析&#x…...
【leetcode】链表part2
24. 两两交换链表中的节点 迭代方法 public static ListNode swapPairs(ListNode head) {// 输入:head [1,2,3,4]// 输出:[2,1,4,3]ListNode dummy new ListNode(0);dummy.next head;ListNode cur dummy;while (cur.next ! null && cur.ne…...

C#数据类型转换
目录 1.常用的数据类型: 编辑1.1别名概念例子: 输出结果: 2.数值类型之间的相互转换: 2.1举例: 编辑输出结果: 1.常用的数据类型: 1.1别名概念例子: 输出结果: 用GetType来获取数据类型的时候,就是指向System.Byte和System.Char这个…...

mybatis-plus逻辑删除的坑
一旦在逻辑字段上加了TableLogic逻辑删除的配置,并且使用mybatis-plus自带的方法时(如果自己用xml写SQL不会出现下面的情况) 查询、修改时会自动排除逻辑删除的数据 当使用mybatis-plus自带的查询方法时,就不用每次查询的时候跟…...

SQL Server基础之游标
一:认识游标 游标是SQL Server的一种数据访问机制,它允许用户访问单独的数据行。用户可以对每一行进行单独的处理,从而降低系统开销和潜在的阻隔情况,用户也可以使用这些数据生成的SQL代码并立即执行或输出。 1.游标的概念 游标是…...

(二)结构型模式:4、组合模式(Composite Pattern)(C++实例)
目录 1、组合模式(Composite Pattern)含义 2、组合模式应用场景 3、组合模式的优缺点 4、组合模式的UML图学习 5、C实现组合模式的简单示例(公司的OA系统) 1、组合模式(Composite Pattern)含义 组合模…...
flask接口请求频率限制
pip install Flask-Limiter Flask-Limiter官方文档 基本使用 默认是用IP作为key进行计数的,你也可以自定义key,具体看官网 from flask import Flask from flask_limiter import Limiter from flask_limiter.util import get_remote_addressapp Flas…...

javaweb监听器和juery技术
监听servlet创建 package com.hspedu.listener;import javax.servlet.ServletContext; import javax.servlet.ServletContextEvent; import javax.servlet.ServletContextListener;/*** 老韩解读* 1. 当一个类实现了 ServletContextListener* 2. 该类就是一个监听器* 3. 该类可…...
C++并发多线程--std::unique_lock的使用
目录 1--std::unique_lock的使用 1-1--std::adopt_lock参数 1-2--std::try_to_lock参数 1-3--std::defer_lock参数 1-4--互斥量所有权转移 1--std::unique_lock的使用 常用成员函数: ① lock(): 加锁; ② unlock(): 解锁; ③ try_lock()…...

【ChatGLM】ChatGLM-6B模型Win+4GB显卡本地部署笔记
ChatGLM-6B是清华大学知识工程和数据挖掘小组发布的一个类似ChatGPT的开源对话机器人,由于该模型是经过约1T标识符的中英文训练,且大部分都是中文,因此十分适合国内使用。 预期环境 本机电脑备注: Win10专业版 32G内存256固态系统…...

青翼科技自研2路250MSPS DA回放FMC子卡模块
FMC150_V30是一款基于VITA57.1规范的2路125MSPS采样率16位分辨率AD采集、2路250MSPS采样率16位分辨率DA回放FMC子卡模块。该模块遵循VITA57.1规范,可直接与符合VITA57.1规范的FPGA载卡配合使用,板卡ADC器件采用ADI公司的AD9268芯片,板卡DAC器…...

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...

select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...