当前位置: 首页 > 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器…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

python打卡day49

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

【WiFi帧结构】

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

跨链模式:多链互操作架构与性能扩展方案

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

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 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时&#xff0c;需要使用外部低速晶振...