浙大数据结构第七周之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器…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...

中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...