GESP:2025-3月等级8-T1-上学
时间限制 : 1 秒
内存限制 : 128 MB
C 城可以视为由 n个结点与 m条边组成的无向图。这些结点依次以1,2,....n标号,边依次以 1,2...m标号。第i条边(1<=i<=m )连接编号为ui 与vi的结点,长度为li米。 小 A 的学校坐落在 C 城中编号为 s的结点。小 A 的同学们共有 q位,他们想在保证不迟到的前提下,每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校,于是找到了聪明的小 A。第 i位同学(1<=i<=q )告诉小 A,他的 家位于编号为hi 的结点,并且他每秒能行走 1 米。请你帮小 A 计算,每位同学从家出发需要多少秒才能到达学校呢?
输入
第一行,四个正整数n,m,s,q ,分别表示 C 城的结点数与边数,学校所在的结点编号,以及小 A 同学们的数量。 接下来m行,每行三个正整数ui,vi,li ,表示 C 城中的一条无向边。 接下来q行,每行一个正整数hi,表示一位同学的情况
输出
共q行,对于每位同学,输出一个整数,表示从家出发到学校的最短时间。
样例
输入
5 5 3 3 1 2 3 2 3 2 3 4 1 4 5 3 1 4 2 5 1 4
输出
4 3 1
提示
数据范围
对于 20% 的测试点,保证q=1 。对于另外20 % 的测试点,保证1<=n<=500 ,1<=m<=500 。
对于所有测试点,保证1<=n<=2 * 10^5 ,1<=m<=2 * 10^5 ,1<=q<=2 * 10^5,1<=ui,vi,s,hi<=n ,1<=li<=10^6 。保证给定的图联通。
———————————————————————————————————————————思路:
以学校为原始的点,Dijkstra算法求学校到每一个点的时间。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=200002;
int n,m,s,t,dis[N];
bool v[N];
struct node
{int v,e;
};
vector<node> q[N];
priority_queue<pair<int,int>>Q;
int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);q[a].push_back(node{c,b});q[b].push_back(node{c,a});}for(int i=1;i<=n;i++){dis[i]=INT_MAX;}dis[s]=0;memset(v,0,sizeof(v));while(!Q.empty()) Q.pop();Q.push(make_pair(0,s));while(!Q.empty()){int wz=Q.top().second;Q.pop();v[wz]=1;for(int i=0;i<q[wz].size();i++){if(dis[q[wz][i].e]>dis[wz]+q[wz][i].v){dis[q[wz][i].e]=dis[wz]+q[wz][i].v;if(!v[q[wz][i].e]){Q.push(make_pair(-dis[q[wz][i].e],q[wz][i].e));}}}}for(int i=1;i<=t;i++){int d;scanf("%d",&d);printf("%d\n",dis[d]);}return 0;
}
相关文章:
GESP:2025-3月等级8-T1-上学
时间限制 : 1 秒 内存限制 : 128 MB C 城可以视为由 n个结点与 m条边组成的无向图。这些结点依次以1,2,....n标号,边依次以 1,2...m标号。第i条边(1<i<m )连接编号为ui 与vi的结点,长度为li米。 小 A 的学校坐落在 C 城中…...
宏碁笔记本电脑擎7PRO搭载的 NVIDIA RTX 5080 显卡安装pytorch
宏碁笔记本电脑擎7PRO搭载的 NVIDIA RTX 5080 显卡是一款高性能移动 GPU,基于 NVIDIA 最新的 Blackwell 架构设计,通过修正架构(Blackwell)、显存类型与带宽(GDDR7、960GB/s)、Tensor Core 与 RT Core 全面…...
Qwen-7B-Chat 本地化部署使用
通义千问 简介 通义千问是阿里云推出的超大规模语言模型,以下是其优缺点: 优点 强大的基础能力:具备语义理解与抽取、闲聊、上下文对话、生成与创作、知识与百科、代码、逻辑与推理、计算、角色扮演等多种能力。可以续写小说、编写邮件、解…...
数据结构,顺序存储线性表
//线性表顺序存储 #include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 #define ElemType int //定义结构体 typedef struct LinearList{ElemType elem[MAXSIZE];int last; }LinearList; //初始化链表 void InitList(LinearList &L){L.last-1; };…...
Matlab轴承故障信号仿真与故障分析
1.摘要 本文介绍了一个基于Matlab的轴承故障信号仿真与分析程序,旨在模拟和分析轴承内圈故障信号的特征。程序首先通过生成故障信号、共振信号和调制信号,添加噪声和离散化处理,构建模拟的振动信号,并保存相关数据。通过快速傅里…...
Git三剑客:工作区、暂存区、版本库深度解析
一、引言:为什么需要理解Git的核心区域? 作为开发者,Git是日常必备的版本控制工具。但你是否曾因以下问题感到困惑? 修改了文件,但 git status 显示一片混乱? git add 和 git commit 到底做了什么&#x…...
stack和queue
1.stack的使用 函数说明接口说明 stack() 构造空的栈 empty 检测stack是否为空 size 返回stack中元素的个数 top 返回栈顶元素的引用 push 将元素val压入stack中 pop 将stack中尾部的元素弹出 void test_stack() {stack<int> st;st.push(1);st.push(2);st.push(3);s…...
【补题】Codeforces Round 1011 (Div. 2) C. Serval and The Formula
题意:给两个数,问你存不存在k使nmn异或m 思路: 为了让nmn异或m成功,很明显有两个数在同一位上最多只能有1个1。因为如果有两个就会导致数字变小,很明显nm是不可能成功的,因为你怎么搞都会有至少一个一模一…...
基于javaweb的SpringBoot汉服文化bbs系统设计与实现(源码+文档+部署讲解)
技术范围:SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...
Vision_Robot
import time import tkinter as tk from tkinter import messagebox from PIL import Image, ImageTk import socket import threading from datetime import datetime import logging import subprocess # 确保导入 subprocess 库 import os import pyautogu…...
爬虫练习案例
案例1: 爬取菜鸟教程左侧导航栏的分类内容: 在pycharm中书写代码。 先倒入相关模块。 import requests from bs4 import BeautifulSoup import lxml.etree as le这个案例写两种写法。 第一种: urlhttps://www.runoob.com/html/html-tuto…...
大数据时代的隐私保护:区块链技术的创新应用
一、引言 在当今数字化时代,大数据已经成为推动社会发展的关键力量。从商业决策到社会治理,从医疗健康到金融服务,数据的价值日益凸显。然而,随着数据的大量收集和广泛使用,隐私保护问题也日益突出。如何在充分利用大…...
力扣刷题-热题100题-第31题(c++、python)
25. K 个一组翻转链表 - 力扣(LeetCode)https://leetcode.cn/problems/reverse-nodes-in-k-group/?envTypestudy-plan-v2&envIdtop-100-liked 常规模拟 根据翻转的长度找到头和尾,进入函数进行翻转 主程序里有循环不断找到头和尾并拼…...
(四)数据检索与增强生成——让对话系统更智能、更高效
上一篇:(三)链式工作流构建——打造智能对话的强大引擎 在前三个阶段,我们已经搭建了一个基础的智能对话,并深入探讨了输入输出处理和链式工作流构建的细节。今天,我们将进入智能对话系统的高级阶段——数…...
Turtle图形化编程知识点汇总:让编程更有趣
友情提示:本文内容由银河易创AI(https://ai.eaigx.com)创作平台gpt-4-turbo模型生成,仅供参考! 在学习编程的过程中,许多初学者会接触到Python的turtle图形库,它是一种图形化编程工具,通过简单的…...
Social GAN(CVPR2018)
文章目录 AbstractIntroductionRelated WorkHuman-Human InteractionRNNs for Sequence PredictionGenerative Modeling MethodProblem DefinitionGenerative Adversarial NetworksSocially-Aware GANPooling ModuleEncouraging Diverse Sample Generation Conclusion paper Ab…...
0201线性回归-机器学习-人工智能
文章目录 1 程序目标2 代码实现3 关键步骤解释4 示例输出5 注意事项结语 以下是一个使用 scikit-learn、pandas和 matplotlib 实现线性回归的完整程序示例。程序包含数据加载、模型训练、预测和可视化。 1 程序目标 加载数据(使用 pandas)数据预处理&am…...
2-Visual Studio 2022 NET开发Windows桌面软件并连接SQL Server数据库
引言 今天尝试Visual Studio 2022 NET开发一个NET桌面软件,并尝试连接SQL Server的数据库,此文章为开发笔记。 --------------------------------------------------------------------------------------------------------------------------------- …...
OpenGL学习笔记(简介、三角形、着色器、纹理、坐标系统、摄像机)
目录 简介核心模式与立即渲染模式状态机对象GLFW和GLAD Hello OpenGLTriangle 三角形顶点缓冲对象 VBO顶点数组对象 VAO元素缓冲对象 EBO/ 索引缓冲对象 IEO 着色器GLSL数据类型输入输出Uniform 纹理纹理过滤Mipmap 多级渐远纹理实际使用方式纹理单元 坐标系统裁剪空间 摄像机自…...
第二十九章:Python-mahotas库:图像处理的高效工具
一、mahotas库简介 mahotas是一个功能强大的Python图像处理库,提供了丰富的图像处理算法和工具,包括图像分割、特征提取、滤波、形态学操作等。它以简洁的API和高效的性能著称,特别适合处理大型图像。资源绑定附上完整资料供读者参考学习&…...
【网络安全】 防火墙技术
防火墙是网络安全防御的重要组成部分,它的主要任务是阻止或限制不安全的网络通信。在这篇文章中,我们将详细介绍防火墙的工作原理,类型以及如何配置和使用防火墙。我们将尽可能使用简单的语言和实例,以便于初学者理解。 一、什么…...
关于Linux系统安装和优化的教程
书籍教程 《Linux 就该这么学》:涵盖多种 Linux 发行版的安装知识,从安装前硬件检测(如硬盘容量需至少 10GB、内存至少 2GB )、软件源选择,到安装步骤(如镜像烧录、启动设置、分区操作 )都有详…...
还是主题混合程序设计
以下是针对您现有代码的完整主题化改造方案,实现跨QML/Qt Widgets的阴影主题系统: 一、主题管理系统核心 // thememanager.h #pragma once #include <QObject> #include <QColor> #include <QMap> #include <QQmlEngine>class…...
【FPGA开发】利用状态机思想点亮流水灯/初学hdlbitsFPGA教程网站
一、状态机思想介绍 状态机是一种用于描述系统行为的形式化模型,它将系统抽象为有限的状态,并通过状态转移来响应外部输入或事件。其核心思想是:系统在任何时刻只处于一个确定的状态,且在不同状态之间按规则切换。状态机是处理明…...
洛谷 P3214 [HNOI2011] 卡农
题目传送门 前言 再次败在 d p dp dp 手下,但是数据范围这么小应该是可以看出是 d p dp dp 的(毕竟对于其他组合数的问题数据范围都是 1 0 9 10^9 109 起步)。 思路 题意简化 现有 1 , 2 , 3 , . . . , n − 1 , n 1, 2, 3, ... , n -…...
智能体和RPA都需要程序思维,如何使用影刀的变量?
欢迎来到涛涛聊AI, 不管AI还是RPA,都需要用到编程思想才能完成批量工作。今天研究了下影刀的变量。 变量类型 根据变量值选择相应的类型,可选择任意一种影刀所支持的数据类型 变量值 指定变量中保存的值,会根据不同的类型设置…...
使用OpenFeign实现服务远程调用
在微服务架构中,由于业务功能的分工不同,我们把项目拆分为多个独立的服务,并常常将其部署在不同的服务器上,这个时候如果服务A的某个功能需要借助服务B来实现,那么这个时候如何去调用就成了问题,目前有一种…...
【移动计算】:AndroidStudio安装和项目搭建【2019:版本3.5.2】
文章目录 1. 下载安装包2. 安装包安装2.1 运行完exe进行安装选择Cancel: Unable SdkInstall Type选择Custom可以选择更新最新版本:这里不选择点击Next勾选 Android Sdk Platform API 虚拟设备选项显示已安装否则也需要勾选设置自定义安装地址:…...
泡棉压缩对显示模组漏光的定位分析及论述
■背景 液晶LCD受到外力或者挤压后,比较容易出现漏光现象即显示mura。一般从结构设计的角度会做如下措施进行整改 1>控制背光和上铁框平整度 ; 2>合理设计液晶模组的厚度和边框大小 ; 3>承载液晶面板的泡棉选取 ; 4>FPC单双层区的设计 ; 5>合理…...
当AI助理接管云计算-走向智能运维的新时代
目录 时代背景 AI在云计算运维上的帮助 新时代产物:WatchAlert 新时代思考 时代背景 代理人工智能:自主决策的未来--Gartner2025十大顶级科技预测第一名 Gartner将代理人工智能列为2025年的顶级技术趋势。该技术通过快速分析用于药物发现的海量数据…...
Day2:前端项目uniapp壁纸实战
先来做一个轮番图。 效果如下: common-style.css view,swiper,swiper-item{box-sizing: border-box; } index.vue <template><view class"homeLayout"><view class"banner"><swiper circular indicator-dots autoplay…...
使用人工智能大模型DeepSeek,如何进行论文润色和去重?
今天我们学习人工智能,如何协助我们进行论文润色和去重。手把手的学习视频地址请访问https://edu.csdn.net/learn/40402/666422 第一步在腾讯元宝对话框中输入如何协助老师做论文润色,通过提问,我们了解了老师写论文润色的步骤和建议。润色的…...
为招聘推荐系统进行相应修改的 Python 实现方案(含协同过滤推荐算法)
下面是为招聘推荐系统进行相应修改的 Python 实现方案。首先是创建数据分析看板,这里借助 Streamlit 库来实现可视化;其次是将协同过滤推荐算法和其他算法(这里采用基于内容的推荐算法)结合,以此提升推荐效果。 impor…...
Spring Boot中自定义注解的创建与使用
🌟 前言 欢迎来到我的技术小宇宙!🌌 这里不仅是我记录技术点滴的后花园,也是我分享学习心得和项目经验的乐园。📚 无论你是技术小白还是资深大牛,这里总有一些内容能触动你的好奇心。🔍 &#x…...
算法思想之双指针(二)
欢迎拜访:雾里看山-CSDN博客 本篇主题:算法思想之双指针二) 发布时间:2025.4.5 隶属专栏:算法 目录 双指针算法介绍对撞指针:快慢指针: 例题有效三角形的个数题目链接题目描述算法思路代码实现 查找总价格为…...
MySQL基础 [一] - 数据库基础
目录 什么是数据库 站在服务器角度理解 站在用户角度理解 为什么不直接使用文件存储呢? 主流数据库 MySQL的基本使用 数据库的使用样例 服务器管理 服务器数据库表之间的关系 MySQL的架构 MySQL语句分类 存储引擎 查看存储引擎 存储引擎对比 什么…...
智能合约的法律挑战与解决之道:技术与法律的交融
智能合约的法律挑战与解决之道:技术与法律的交融 智能合约的诞生,为区块链技术的应用打开了新的大门。从简单的自动化交易到复杂的去中心化自治组织(DAO),智能合约正在推动全球经济迈向去信任化的新时代。然而&#x…...
MySQL基础 [一] - Ubuntu版本安装
目录 预安装 先查看自己操作系统的版本 添加MySQL APT下载源 下载 安装 正式安装 查看MySQL状态 打开MySQL 预安装 先查看自己操作系统的版本 lsb_release -a 添加MySQL APT下载源 下载 下载发布包 下载地址 : https://dev.mysql.com/downloads/repo/apt/ 这里下…...
cursor机器码重置
1、下载vscode插件 cursor-fake-machine-0.0.2 2、将插件拖入拓展 3、彻底将cursor账号退出 setting -> Manage -> 退出账号 4、打开cursor,ctrlshiftp ,输入fake,点击确定...
深度学习的疑问--综合【2】:像CNN,GNN,transformer等这些模型都是用于提取特征,然后经过全连接层实现分类的吗?
总结: CNN,GNN,transformer等这些模型都是用于提取特征;FC、MLP等用于实现分类,MLP即是多个FC组成的。 是的,从高层次来看,CNN(卷积神经网络)、GNN(图神经网络…...
基于编程的运输设备管理系统设计(vue+springboot+ssm+mysql8.x)
基于编程的运输设备管理系统设计(vuespringbootssmmysql8.x) 运输设备信息管理系统是一个全面的设备管理平台,旨在优化设备管理流程,提高运输效率。系统提供登录入口,确保只有授权用户可以访问。个人中心让用户可以查…...
SpringBoot整合MyBatis
一、SpringBoot整合MyBatis 步骤1:创建新模块,选择Spring初始化,并配置模块相关基础信息 步骤2:选择当前模块需要使用的技术集(MyBatis、MySQL) 步骤3:设置数据源参数 spring:datasource:dr…...
kali——masscan
目录 前言 使用方法 前言 Masscan 是一款快速的端口扫描工具,在 Kali Linux 系统中常被用于网络安全评估和渗透测试。 使用方法 对单个IP进行端口扫描: masscan -p11-65535 192.168.238.131 扫描指定端口: masscan -p80,22 192.168.238.131…...
数字化转型中的开源AI智能客服与S2B2C商城小程序的融合创新
摘要 数字经济时代,企业需通过技术重构用户交互与供应链体系。本文以“开源AI智能客服”“AI智能名片”及“S2B2C商城小程序”为核心,研究三者如何通过技术协同与场景化应用实现企业营销、客户服务与供应链管理的智能化升级。通过案例分析、技术架构设…...
2-Docker常用命令
1. Docker 帮助启动类命令 1.1 启动 docker: systemctl start docker [rootlocalhost ~]# systemctl start docker1.2 停止 docker: systemctl stop docker [rootlocalhost ~]# systemctl stop docke1.3 重启 docker: systemctl restart d…...
理解OSPF 特殊区域NSSA和各类LSA特点
本文基于上文 理解OSPF Stub区域和各类LSA特点 在理解了Stub区域之后,我们再来理解一下NSSA区域,NSSA区域用于需要引入少量外部路由,同时又需要保持Stub区域特性的情况 一、 网络总拓扑图 我们在R1上配置黑洞路由,来模拟NSSA区域…...
Chapter01_绪论
文章目录 数字图像处理导论⭐图像的分类数字图像处理的概念(狭义)⭐数字图像处理的基本特征图像分析 ⭐数字图像处理的组成⭐数字图像处理研究的基本内容 数字图像处理导论 ⭐图像的分类 模拟图像:二维空间和亮度值都是连续(值&a…...
SDL显示YUV视频
文章目录 1. **宏定义和初始化**2. **全局变量**3. **refresh_video_timer 函数**4. **WinMain 函数**主要功能及工作流程:总结: 1. 宏定义和初始化 #define REFRESH_EVENT (SDL_USEREVENT 1) // 请求画面刷新事件 #define QUIT_EVENT (SDL…...
频域滤波函数 To 空域冲激响应函数
从频域滤波函数 H ( u , v ) H(u, v) H(u,v)到空域冲激响应函数 h ( x , y ) h(x, y) h(x,y)的变换。 不是冈萨雷斯这么简单的IDFT,有两次移位。这么费劲是因为DFT定义在第一象限。而且要求滤波器的尺寸为奇数,零的个数没有影响。 逆中心移位变换&…...
【C++】C++11<包装器没写>
文章目录 一、初始化列表的统一1.列表初始化2.initializer_list 二、声明1.auto2.decltype3.nullptr 三、范围for四、智能指针五、STL中的变化1.新容器arrayforward_list 2.接口 六、右值引用1.左值引用和右值引用2.右值引用的使用场景和意义3.左值引用和右值引用的价值和场景4…...