当前位置: 首页 > news >正文

浙大数据结构第七周之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 旅游规划

题目详情&#xff1a; 有了一张自驾旅游路线图&#xff0c;你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序&#xff0c;帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的&#xff0c;那么需要输出最便宜的…...

RocketMQ双主双从同步集群部署

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

分类预测 | MATLAB实现EVO-CNN多输入分类预测

分类预测 | MATLAB实现EVO-CNN多输入分类预测 目录 分类预测 | MATLAB实现EVO-CNN多输入分类预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.MATLAB实现EVO-CNN多输入分类预测 2.代码说明&#xff1a;量谷优化卷积神经网络的数据分类预测&#xff1a;要求于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工程&#xff08;Maven结构&#xff09;【第二步】设置tomcat服务器&#xff0c;加…...

phpstorm配置ftp同步文件到服务器

这里的默认快捷键 不是 CtrlS &#xff1b;需要设置快捷键&#xff0c;这里原来是save all操作时上传文件到服务器&#xff1b; ** 设置好快捷键后按 CtrlS就会同步文件&#xff08;添加删除文件后保存&#xff0c;服务器也会同步&#xff09; ** 搜索出save all 后&#xf…...

前端jd要求:了解一门后端开发语言优先 解决方案之Node.js

前端jd要求&#xff1a;了解一门后端开发语言优先 解决方案之Node.js 前言常见的后端开发语言一、什么是 Node.js二、学习 Node.js 的前置知识三、学习 Node.js 的步骤1、Node.js 的安装2、Node.js 的基本语法和 API模块导入和导出文件读写操作HTTP 服务器命令行参数 3、Node.j…...

什么是ServiceMesh(Istio一)

现在最火的后端架构无疑是微服务了&#xff0c;微服务将之前的单体应用拆分成了许多独立的服务应用&#xff0c;每个微服务都是独立的&#xff0c;好处自然很多&#xff0c;但是随着应用的越来越大&#xff0c;微服务暴露出来的问题也就随之而来了&#xff0c;微服务越来越多&a…...

【腾讯云 Cloud Studio 实战训练营】Hexo 框架 Butterfly 主题搭建个人博客

什么是Cloud Studio Cloud Studio 是基于浏览器的集成式开发环境&#xff08;IDE&#xff09;&#xff0c;为开发者提供了一个永不间断的云端工作站。用户在使用 Cloud Studio 时无需安装&#xff0c;随时随地打开浏览器就能在线编程。 ​ Hexo 博客成品展示 本人博客如下&…...

搭建Excel服务器

1、下载Excel服务器 下载地址 2、解压文件 3、打开服务器 4、服务器运行信息 5、连接测试 打开客户端 6、登录到服务器 默认账号 密码 admin 3 修改文件保存路径(服务器端点击配置) 7、客户端整体界面 8、配置权限 9、设计模板 10、其他用户登录就可以填写信息 11、用户&#…...

渗透测试成功的8个关键

渗透测试 (penetration test)并没有一个标准的定义&#xff0c;国外一些安全组织达成共识的通用说法是&#xff1a;渗透测试是通过模拟恶意黑客的攻击方法&#xff0c;来评估计算机网络系统安全的一种评估方法。这个过程包括对系统的任何弱点、技术缺陷或漏洞的主动分析&#x…...

【leetcode】链表part2

24. 两两交换链表中的节点 迭代方法 public static ListNode swapPairs(ListNode head) {// 输入&#xff1a;head [1,2,3,4]// 输出&#xff1a;[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别名概念例子: 输出结果&#xff1a; 2.数值类型之间的相互转换: 2.1举例: ​编辑输出结果: 1.常用的数据类型: 1.1别名概念例子: 输出结果&#xff1a; 用GetType来获取数据类型的时候&#xff0c;就是指向System.Byte和System.Char这个…...

mybatis-plus逻辑删除的坑

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

SQL Server基础之游标

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

(二)结构型模式:4、组合模式(Composite Pattern)(C++实例)

目录 1、组合模式&#xff08;Composite Pattern&#xff09;含义 2、组合模式应用场景 3、组合模式的优缺点 4、组合模式的UML图学习 5、C实现组合模式的简单示例&#xff08;公司的OA系统&#xff09; 1、组合模式&#xff08;Composite Pattern&#xff09;含义 组合模…...

flask接口请求频率限制

pip install Flask-Limiter Flask-Limiter官方文档 基本使用 默认是用IP作为key进行计数的&#xff0c;你也可以自定义key&#xff0c;具体看官网 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的使用 常用成员函数&#xff1a; ① lock(): 加锁&#xff1b; ② unlock(): 解锁&#xff1b; ③ try_lock()…...

【ChatGLM】ChatGLM-6B模型Win+4GB显卡本地部署笔记

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

青翼科技自研2路250MSPS DA回放FMC子卡模块

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

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

前端导出带有合并单元格的列表

// 导出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米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

(一)单例模式

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