#P0761. [NOIP2012普及组] 文化之旅

news/2024/4/20 14:03:57/

题目描述

有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习任何一种文化超过一次(即如果他学习了某种文化,则他就不能到达其他有这种文化的国家)。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同,有些文化会排斥外来文化(即如果他学习了某种文化,则他不能到达排斥这种文化的其他国家)。

现给定各个国家间的地理关系,各个国家的文化,每种文化对其他文化的看法,以及这位使者游历的起点和终点(在起点和终点也会学习当地的文化),国家间的道路距离,试求从起点到终点最少需走多少路。

输入格式

第一行为五个整数 N,K,M,S,TN,K,M,S,T,每两个整数之间用一个空格隔开,依次代表国家个数(国家编号为11 到 NN),文化种数(文化编号为 11 到 KK),道路的条数,以及起点和终点的编号(保证 SS 不等于 TT);

第二行为 NN个整数,每两个整数之间用一个空格隔开,其中第 ii个数 C_iCi​,表示国家 ii的文化为 C_iCi​。

接下来的 KK行,每行 KK 个整数,每两个整数之间用一个空格隔开,记第ii 行的第 j 个数为 a_{ij}aij​,a_{ij}= 1aij​=1 表示文化 ii 排斥外来文化jj(ii 等于 jj 时表示排斥相同文化的外来人),a_{ij}= 0aij​=0 表示不排斥(注意 ii 排斥 jj 并不保证 jj 一定也排斥 ii)。

接下来的 MM 行,每行三个整数 u,v,du,v,d,每两个整数之间用一个空格隔开,表示国家 uu与国家 vv有一条距离为dd的可双向通行的道路(保证uu不等于 vv,两个国家之间可能有多条道路)。

输出格式

一个整数,表示使者从起点国家到达终点国家最少需要走的距离数(如果无解则输出-1−1)。

输入数据 1

2 2 1 1 2 
1 2 
0 1 
1 0 
1 2 10

Copy

输出数据 1

-1

Copy

输入数据 2

2 2 1 1 2 
1 2 
0 1 
0 0 
1 2 10

Copy

输出数据 2

10

Copy

提示

输入输出样例说明11

由于到国家 22 必须要经过国家11,而国家22的文明却排斥国家 11 的文明,所以不可能到达国家 22。

输入输出样例说明22

路线为11 ->22

【数据范围】

对于 100%的数据,有2≤N≤1002≤N≤100

1≤K≤1001≤K≤100

1≤M≤N^21≤M≤N2

1≤k_i≤K1≤ki​≤K

1≤u, v≤N1≤u,v≤N

1≤d≤1000,S≠T,1≤S,T≤N1≤d≤1000,S=T,1≤S,T≤N

NOIP 2012 普及组 第四题

代码:

#include <cstdio>
#include <cstring>
int n,k,m,s,t,country[105],first[20005],next[20005],v[20005],w[20005];
int wh[105][105],cnt,head,tail,q[100005],dis[105];
int q1[100005][105];
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();if (ch=='-'){f=-1;ch=getchar();}while ((ch<'0')||(ch>'9')) ch=getchar();while ((ch>='0')&&(ch<='9')){x=x*10+ch-48;ch=getchar();}return f*x;
}
inline void spfa(int s)
{memset(dis,0x3f3f3f3f,sizeof(dis));//dis数组记录的是s点到所有点的距离 dis[s]=0;head=0;tail=1;q[1]=s;q1[1][0]=1;//q1[i][0]记录的是知道了多少种文化 q1[1][1]=country[s];while (head<tail){head=head%100000+1; for (int i=first[q[head]];i;i=next[i]){int k=v[i];//k为目标点 bool bo=0;for (int j=1;j<=q1[head][0];j++)//判断目标点可否到达 if (wh[country[k]][q1[head][j]]||(country[k]==q1[head][j])){bo=1;break;}if (bo) continue;//不可到达,则跳过 if (dis[q[head]]+w[i]<dis[k])//如果可以使距离变短的话,就加入 {dis[k]=dis[q[head]]+w[i];tail=tail%100000+1;q[tail]=k;q1[tail][0]=q1[head][0]+1;for (int j=1;j<=q1[head][0];j++)q1[tail][j]=q1[head][j];q1[tail][q1[tail][0]]=country[k];}}}//下面判断输出 if (dis[t]==0x3f3f3f3f){printf("-1\n");return;} else{printf("%d\n",dis[t]);return;}
}
int main()
{n=read(),k=read(),m=read(),s=read(),t=read();for (int i=1;i<=n;i++) country[i]=read();for (int i=1;i<=k;i++)for (int j=1;j<=k;j++) wh[i][j]=read();for (int i=1;i<=m;i++){int x,y,z;x=read(),y=read(),z=read();next[++cnt]=first[x];first[x]=cnt;v[cnt]=y;w[cnt]=z;next[++cnt]=first[y];first[y]=cnt;v[cnt]=x;w[cnt]=z;}spfa(s);return 0;
}


http://www.ppmy.cn/news/1003829.html

相关文章

寻找旋转排序数组中的最小值——力扣153

文章目录 题目描述解法 二分法 题目描述 解法 二分法 int findMin(vector<int>& nums){int l0, rnums.size()-1;while(l<r){int mid (lr)/2;if(nums[mid]<nums[r]) rmid;else lmid1;}return nums[l];}

机器学习笔记 - YOLO-NAS 最高效的目标检测算法之一

一、YOLO-NAS概述 YOLO(You Only Look Once)是一种对象检测算法,它使用深度神经网络模型,特别是卷积神经网络,来实时检测和分类对象。该算法首次在 2016 年由 Joseph Redmon、Santosh Divvala、Ross Girshick 和 Ali Farhadi 发表的论文《You Only Look Once: Unified, Re…

python:np.tile函数

python&#xff1a;np.tile函数 np.tile(P0, (n, 1, 1))tile的(arr,(a,b,c,d))的abcd&#xff1a;在batch、c、h、w四个维度分别拷贝。 第三、第四个参数c&#xff0c;d&#xff1a;将原数据arr拷贝&#xff08;从行的维度拷贝c份&#xff0c;从列的维度拷贝d份&#xff09;&…

机器学习06 数据准备-(利用 scikit-learn基于Pima Indian数据集作 数据特征选定)

什么是数据特征选定? 数据特征选定&#xff08;Feature Selection&#xff09;是指从原始数据中选择最相关、最有用的特征&#xff0c;用于构建机器学习模型。特征选定是机器学习流程中非常重要的一步&#xff0c;它直接影响模型的性能和泛化能力。通过选择最重要的特征&#…

go-zero超强工具goctl的常用命令api,rpc,model及其构建的服务解析

goctl api 详情移步&#xff1a; go-zero的路由机制解析 基于go-zero的api服务刨析并对比与gin的区别 goctl rpc goctl支持多种rpc&#xff0c;较为流行的是google开源的grpc&#xff0c;这里主要介绍goctl rpc protoc的代码生成与使用。 protoc是grpc的命令&#xff0c;作用…

【eNSP】静态路由

【eNSP】静态路由 原理网关路由表 实验根据图片连接模块配置路由器设备R1R2R3R4 配置PC的IP地址、掩码、网关PC1PC2PC3 配置静态路由查看路由表R1R2R3R4测试能否通信 原理 网关 网关与路由器地址相同&#xff0c;一般路由地址为.1或.254。 网关是当电脑发送的数据的目标IP不在…

Dockerfile构建MySQL镜像

创建工作目录 [rootlocalhost ~]# mkdir mysql [rootlocalhost ~]# cd mysql/ 编写Dockerfile文件 [rootlocalhost mysql]# vim Dockerfile FROM centos:7 MAINTAINER Crushlinux <crushlinux163.com> #安装mariadb数据库 RUN yum install -y mariadb mariadb-server mar…

配置root账户ssh免密登录并使用docker-machine构建docker服务

简介 Docker Machine是一种可以在多种平台上快速安装和维护docker运行环境&#xff0c;并支持多种平台&#xff0c;让用户可以在很短时间内在本地或云环境中搭建一套docker主机集群的工具。 使用docker-machine命令&#xff0c;可以启动、审查、停止、重启托管的docker 也可以…

MPP架构和Hadoop架构的区别

1. 架构的介绍 mpp架构是将许多数据库通过网络连接起来&#xff0c;相当于将一个个垂直系统横向连接&#xff0c;形成一个统一对外的服务的分布式数据库系统。每个节点由一个单机数据库系统独立管理和操作该物理机上的的所有资源&#xff08;CPU&#xff0c;内存等&#xff09…

SAP ABAP直接调用标准程序取数

项目上有时候会遇到一些报表开发&#xff0c;可能时基于MB51的凭证查询后处理&#xff0c;或基于库存清单进行操作。这种需求其实在FS和开发上是都可以简化的&#xff0c;直接调用标准的报表数据进行加工&#xff0c;后续方案的调整等等对功能影响较小。 调用代码模板 if IV_…

第四章 数据库安全性

问题的提出 &#xff08;1&#xff09;数据库的一大特点是数据可以共享 &#xff08;2&#xff09;数据共享必然带来数据库的安全性问题 &#xff08;3&#xff09;数据库系统中的数据共享不能是无条件的共享 这就引发了数据库安全性问题 1.数据库安全性概述 数据库的安全性…

Hutool中 常用的工具类和方法

文章目录 日期时间工具类 DateUtil日期时间对象-DateTime类型转换工具类 Convert字符串工具类 StrUtil数字处理工具类 NumberUtilJavaBean的工具类 BeanUtil集合操作的工具类 CollUtilMap操作工具类 MapUtil数组工具-ArrayUtil唯一ID工具-IdUtilIO工具类-IoUtil加密解密工具类 …

音频光耦合器

音频光耦合器是一种能够将电信号转换为光信号并进行传输的设备。它通常由发光二极管&#xff08;LED&#xff09;和光敏电阻&#xff08;光电二极管或光敏电阻器&#xff09;组成。 在音频光耦合器中&#xff0c;音频信号经过放大和调节后&#xff0c;被转换为电流信号&#xf…

基于 Flink Paimon 实现 Streaming Warehouse 数据一致性管理

摘要&#xff1a;本文整理自字节跳动基础架构工程师李明&#xff0c;在 Apache Paimon Meetup 的分享。本篇内容主要分为四个部分&#xff1a; 背景 方案设计 当前进展 未来规划 点击查看原文视频 & 演讲PPT 一、背景 ​ 早期的数仓生产体系主要以离线数仓为主&#xf…

《命运》阅读笔记

《命运》阅读笔记 2023年5月17号在杭州的小屋读完&#xff0c;我读完后&#xff0c;脑海里经常把余华的《活着》和这本《命运》的故事情节搞混淆&#xff0c;几乎都是讲着生活的苦难。全文以阿太&#xff08;外婆的妈妈&#xff09;的视角&#xff0c;在她九十九岁的人生里&…

一文学透设计模式——工厂模式

工厂模式 概念 牛马人生公司最近开启了线上直播&#xff0c;直播中牛马人生公司宣称他们建造了一家世界上最为先进的工厂&#xff0c;任何人只要去到工厂面前&#xff0c;告诉工厂你要什么牌子的汽车&#xff0c;工厂就会给你一辆什么牌子的汽车。 这引起了粉丝朋友的注意&a…

Java中运算符要注意的一些点

目录 1. 算术运算符 1. 1 基本四则运算符&#xff1a;加减乘除模( - * / %) 1.2. 增量运算符 - * % 2. 关系运算符 3. 逻辑运算符 3.1. 逻辑与 && 3.2. 逻辑 || 3.3. 逻辑非 ! 3.4. 短路求值 4. 位运算符 4.1. 按位与 &: 如果两个二进制位都是 …

使用中间人攻击的arp欺骗教程

文章目录 前言一、查看网络接口配置第 1 步&#xff1a;从受害者处获取 IP 配置第 2 步&#xff1a;在 Linux 中打开数据包转发第 3 步&#xff1a;使用 arpspoof 将包重定向到您的计算机步骤4&#xff1a;拦截来自路由器的包裹步骤5&#xff1a;从目标的浏览器历史记录中嗅探图…

【C++】BSTree 模拟笔记

文章目录 概念插入和删除非递归实现中的问题递归中的引用简化相关OJ复习直达 概念 由下面二叉搜索树的性质可以知道&#xff0c;中序遍历它便可以得到一个升序序列&#xff0c;查找效率高&#xff0c;小于往左找&#xff0c;大于往右走。最多查找高度次&#xff0c;走到到空&am…

一文了解MySQL中的多版本并发控制作者

最近在阅读《认知觉醒》这本书&#xff0c;里面有句话非常打动我&#xff1a;通过自己的语言&#xff0c;用最简单的话把一件事情讲清楚&#xff0c;最好让外行人也能听懂。 也许这就是大道至简&#xff0c;只是我们习惯了烦琐和复杂。 希望借助今天这篇文章&#xff0c;能用…