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

CSUSTOJ 搬砖(状压dp)

题目链接
在这里插入图片描述
emmm显然的状压dp
我们定义dp[状态][j] 表示该状态下以j为终点的最短时间
先把存图floyd一下,然后开始状压dp处理。
对于K个任务,只需要记录每个经过的点的二进制位就OK,把任务合成一个带有1号起点的状态,查询输出该状态下以目标终点结尾就OK

 #include<bits/stdc++.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)using namespace std;ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂%
ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元   (分子*qp(分母,mod-2,mod))%mod;ll G[50][50];
const int N=(1<<19);
ll dp[N+20][22];
signed main()
{ll n,m,kk;read(n);read(m);read(kk);memset(G,inf,sizeof(G));for(int i=1; i<=m; i++){ll u,v,w;read(u);read(v);read(w);u--;v--;G[u][v]=G[v][u]=min(G[u][v],w);}for(int i=0; i<n; i++){G[i][i]=0;}for(int i=0; i<n; i++){for(int j=0; j<n; j++){for(int k=0; k<n; k++){G[j][k]=min(G[j][k],G[j][i]+G[i][k]);}}}memset(dp,inf,sizeof(dp));dp[0][0]=0;dp[1][0]=0;for(int i=1; i<(1<<n); i++){for(int j=0; j<n; j++){if((1<<j)&i){for(int k=0; k<n; k++){if(k!=j&&(!(i&(1<<k)))){dp[i+(1<<k)][k]=min(dp[i+(1<<k)][k],dp[i][j]+G[j][k]);}}}}}for(int i=1; i<=kk; i++){ll cnt=1;ll op;read(op);op--;if(!(cnt&(1<<op)))cnt=cnt+(1<<op);ll num;read(num);for(int j=1; j<=num; j++){ll x;read(x);x--;if(!(cnt&(1<<x)))cnt=cnt+(1<<x);}printf("%lld\n",dp[cnt][op]);}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.exyb.cn/news/show-35421.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

爬虫学习——库的安装问题及解决方案

关于No module named ‘Cryptodome’ 一直很想爬网易云的评论&#xff0c;但爬虫还没学精&#xff0c;然后去找了一篇博客来试试&#xff01;接着关于库的安装磨了我好久…找了好多资料没成功&#xff0c;最后在老师以及自己不断尝试下&#xff0c;终于成功了&#xff01;感动…...

Vuejs010---自定义指令

1-1 自定义全局指令 指令与属性相似&#xff0c;是对指定元素样式或行为的赋予。 我们可以在实际项目开发中自定义一些我们所需的指令来有效的管 理元素。 在页面中自定义的全局指令&#xff0c;可以为每一个 vm 对象中的元素提供服务&#xff0c;只要 vm 中的标签引用了全局指…...

Keyhole Markup Language (KML)

5. KML-Keyhole Markup Language From https://developers.google.com/kml/documentation/kml_tut?hlzh-CN KML 是一种文件格式&#xff0c;用于在地球浏览器&#xff08;例如 Google 地球、Google 地图和谷歌手机地图&#xff09;中显示地理数据。KML 使用含有嵌套的元素和…...

Linux企业运维——Kubernetes(十六)容器资源监控

Linux企业运维——Kubernetes&#xff08;十六&#xff09;容器资源监控 文章目录Linux企业运维——Kubernetes&#xff08;十六&#xff09;容器资源监控1、Metrics-Server1.1、Metrics-Server简介1.2、Metrics-Server部署2、Dashboard2.1、Dashboard部署2.2、Dashboard可视化…...

KNN算法基础教学

目录 1、KNN算法概述 2、什么是knn算法 3、算法原理解析 3.1、通用步骤 3.2、k的取值对预测结果的影响 3.3、k的选取 4、实战应用 &#xff08;癌症检测数据&#xff09; 完整代码&#xff1a; 1、KNN算法概述 KNN可以说是最简单的分类算法之一&#xff0c;同时&#xff0…...

2022.08.23-力扣刷题(222、789、199、124、257、404)

222. 完全二叉树的节点个数 题目链接&#xff1a; https://leetcode-cn.com/problems/count-complete-tree-nodes/ 方法一&#xff1a;迭代法层序遍历 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # …...

idea复制当前行快捷键

仅作为记录&#xff0c;大佬请跳过。 在该行的任何位置&#xff0c;直接用ctrl和c即可 参考 感谢大佬博主文章&#xff1a;传送门...

不抛弃异常值的几种情况

异常数据是数据分布的常态,处于特定分布区域或范围之外的数据 通常会被定义为异常或“噪音”。产生数据“噪音”的原因很多,例如业务 运营操作、数据采集问题、数据同步问题等。对异常数据进行处理前, 需要先辨别出到底哪些是真正的数据异常。 从数据异常的状态看分为两 种…...

微信小程序从云开发到上线

文章目录一、创建项目二、云函数三、静默登录四、获取用户信息五、使用缓存六、同页面数据操作七、不同页面数据传递八、页面跳转九、检查版本更新十、上线​ 前段时间自己做了一个云开发微信小程序&#xff0c;发现并不复杂&#xff0c;有前端基础的可以试一下。这里主要简单说…...

23种设计模式

一、什么是设计模式 设计模式&#xff08;Design pattern&#xff09;是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。 毫无疑问&#xff0c;设计模式于己于他人于系统都是多…...

Nacos 2.0.2正式版发布

一、介绍Nacos Nacos 致力于帮助您发现、配置和管理微服务。Nacos 提供了一组简单易用的特性集&#xff0c;帮助您快速实现动态服务发现、服务配置、服务元数据及流量管理。 Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。 Nacos 是构建以“服务”为中心的现代应用…...

OSI七层和TCP/IP四层的关系

OSI七层和TCP/IP四层的关系 1.1 OSI引入了服务、接口、协议、分层的概念&#xff0c;TCP/IP借鉴了OSI的这些概念建立TCP/IP模型。 1.2 OSI先有模型&#xff0c;后有协议&#xff0c;先有标准&#xff0c;后进行实践&#xff1b;而TCP/IP则相反&#xff0c;先有协议和应用再提…...

spring框架的各种注解基本意思

//在 spring 配置文件中开启生成代理对象 <!-- 开启 Aspect 生成代理对象--> <aop:aspectj-autoproxy></aop:aspectj-autoproxy>Autowired //根据属性类型进行自动装配 Aspect //生成代理对象 Qualifier //根据名称进行注 Resource //可以根据类型注…...

【Java45】旅游案例:数据回显,注销/退出,首页类别显示,精选

文章目录1.登陆数据回显1.1 前端2.登陆案例_注销/退出3.首页类别显示3.1 web3.2 service3.3 dao4.精选4.1 web4.2 service4.3 dao4.4 前端1.登陆数据回显 如上前端写在header.html中。 1.1 前端 //header.html <!-- 头部 start --><header id"header2"&g…...

简单介绍下Python解释器

当我们编写Python代码时&#xff0c;我们得到的是一个包含Python代码的以.py为扩展名的文本文件。要运行代码&#xff0c;就需要Python解释器去执行.py文件。 由于整个Python语言从规范到解释器都是开源的&#xff0c;所以理论上&#xff0c;只要水平够高&#xff0c;任何人都…...

出现了,Mac也可以玩的简单扫雷(1.0版本)

总体思路: 1.随机生成雷区 2.将每一个方块旁边有几个雷的数量算出来 3.不断的输入想要翻的方块 4.判断是否输赢 5.改变此方块的状态 直接上代码: #include <iostream> #include <ctime> #include <chrono> //计时头文件 #include <string.h> …...

axios跨域问题

项目配置 vue-cli3vue2element-ui-2.15.3 在网上找了很多方案&#xff0c;但是都没有生效&#xff0c;最后是前端添加了一段代码&#xff0c;后台添加了一段代码 解决了 添加了headers的配置 const instance axios.create({// baseURL: http://mall.huolida.com/,// baseUR…...

原创-Kafka原理

Kafka原理 2017年09月22日 22:39:45317人阅读 评论(0) 收藏 举报 分类&#xff1a; Kafka&#xff08;1&#xff09; 目录(?)[] Kafka 这段时间研究RabbitMQ、Kafka、RocketMQ消息队列&#xff0c;发现对她们原理的介绍都过于简单&#xff0c;所以整理了众多资料&…...

ef dbcontext

dbcontext class 用来crud数据库&#xff0c;也用来配置实体类&#xff0c;关系映射&#xff0c;缓存&#xff0c;事务&#xff0c;变化追踪等 using System.Data.Entity;public class SchoolContext : DbContext {public SchoolContext(){}// Entities public DbSet&l…...

【ACWing】1273. 天才的记忆

题目地址&#xff1a; https://www.acwing.com/problem/content/1275/ 从前有个人名叫WNB&#xff0c;他有着天才般的记忆力&#xff0c;他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题&#xff08;专门考验记忆力的啊&#xff01;&#xff09;&#xff0c;如果谁能轻…...

Gerrit简单介绍

什么是Gerrit&#xff1f; Gerrit是一个web代码评审工具&#xff0c;它基于git版本控制系统。Gerrit旨在提供一个轻量级框架&#xff0c;用于在代码入库之前对每个提交进行审阅。‎Gerrit会记录每一次提交的代码修改&#xff0c;但只有它们被审阅和接收后才能合入成为项目的一部…...

Mysql online DDL 线上无锁添加索引

只能通过ALTER TABLE不能create index ALTER TABLE tbl_name ADD PRIMARY KEY (column), ALGORITHMINPLACE, LOCKNONE; 参数说明&#xff1a; ALGORITHMINPLACE 更优秀的解决方案&#xff0c;在当前表加索引&#xff0c;步骤&#xff1a; 1.创建索引(二级索引)数据字典 2.加…...

C语言 指针声明和定义 - C语言零基础入门教程

目录 一.指针简介 1.内存2.内存地址3.指针声明 二.指针类型三.声明并初始化一个指针 1.声明指针并直接初始化 – 推荐2.先声明指针在初始化 – 不推荐 四.查看指针地址和指针的值五.NULL 指针 – 空指针六.重点总结七.猜你喜欢 零基础 C/C 学习路线推荐 : C/C 学习目录 >&g…...

[益智题] —— 在 5 5 5 1 间添加运算符号使结果为24

题目结果&#xff1a; 5 * &#xff08;5 - 1 / 5&#xff09; 24 题目解析&#xff1a; 巧妙利用分数运算消去分母得到分子。...

JVM运行时数据区(内存模型)

Java程序执行过程&#xff1a; 如上图所示&#xff0c;首先Java源代码文件(.java后缀)会被Java编译器编译为字节码文件(.class后缀)&#xff0c;然后由JVM中的类加载器加载各个类的字节码文件。加载完毕之后&#xff0c;交由JVM执行引擎执行。 在整个程序执行过程中&#xff0…...

7-图像分割

图像分割&#xff0c;其实就是像素级别的分类 目标检测的是object级别的&#xff0c;不包含背景 图像分类-语义分割把图片的里面的像素进行划分 包含背景 目标检测-实例分割&#xff0c;边框轮廓划分起来 不包含背景 全景分割 语义分割和实例分割结合 3 应用 数据集和评价…...

RBCADS 滚动轴承计算机辅助设计系统 7A单列圆锥滚子轴承公制和英制计算机辅助设计软件

[三维滚动轴承CAD系统RBCADS ]是专门用于滚动轴承产品设计的计算机软件。使用该系列软件可以快速设计出绝大多数结构的轴承产品&#xff0c;对于提高企业对市场的快速反应能力&#xff0c;提高轴承产品的设计效率和质量&#xff0c;减少设计错误将发挥积极的作用。目前轴承行业…...

使用idea创建JavaWeb项目

使用idea创建JavaWeb项目 【第一步】 File---New---Project 【第二步】 选择Java Enterprise版本&#xff0c;然后配置tomcat 注意&#xff1a;这里关联的tomcat home指的是tomcat的解压目录&#xff08;bin目录的上一级目录&#xff09;&#xff1b; 【第三步】 选择使用模板…...

RabbitMQ快速初始化安装图文详细步骤

RabbitMQ 是一个流行的开源消息队列系统。用于在分布式系统中存储转发消息&#xff0c;在易用性、扩展性、高可用性等方面表现不俗。 小九今天为大家带来RabbitMQ的快速初始化安装图文详细步骤~希望能够帮到大家&#xff01; 初始化安装 常规的安装&#xff0c;需要经过前期下…...

Filecoin减产即将来临IPFS黄金时间你抓住了么?

按照Filecoin官方之前发布的信息&#xff0c;Filecoin首次产量下降时间段是2021年4月十五号&#xff0c;包括SAFT,基金会&#xff0c;团队和生态的释放&#xff0c;4月十五号SAFT半年期所有线性释放结束&#xff0c;单天生产降低43.2%,也就是过后流动到市场的Filecoin将每日降低…...

【Spring系列】- Spring循环依赖

Spring循环依赖 &#x1f604;生命不息&#xff0c;写作不止 &#x1f525; 继续踏上学习之路&#xff0c;学之分享笔记 &#x1f44a; 总有一天我也能像各位大佬一样 &#x1f3c6; 一个有梦有戏的人 怒放吧德德 &#x1f31d;分享学习心得&#xff0c;欢迎指正&#xff0c;大…...

将多个PDF文件整合成一个文件

pdfFactory不仅可以将单个文件创建为PDF文件进行打印&#xff0c;还可以将多个文件整合为一个PDF文件&#xff0c;同时&#xff0c;也可以随时删除其中的一些文件&#xff0c;创建新的PDF文件。 图1&#xff1a;pdfFactory工具界面 一、 载入第一个文档 我们今天将以Word文档…...

wps总结

wps: 1、中文宋体&#xff0c;英文新罗马。做好在右上角《标题正文》里&#xff0c;设置好。 2、注意书签的运用&#xff0c;视图>大纲。可方便自动生成目录。 3、注意页边距设置。页面布局>页边距。 excel: 1、单元格内换行&#xff0c;altenter&#xff1b;...

用Unity实现FXAA

用Unity实现FXAAFXAA是现代的常用抗锯齿手段之一&#xff0c;这次我们来在Unity中从零开始实现它。 首先我们来看一个测试场景&#xff0c;我们在Game视角下将scale拉到2x&#xff1a; 可以看到画面的锯齿比较严重&#xff0c;下面我们将一步一步地实现FXAA&#xff0c;消除锯…...

第1章 自动化测试基础

1.1 软件测试分类 根据项目流程阶段划分软件测试 1&#xff09; 单元测试&#xff1a;又称模块测试&#xff0c;是对程序中的单个子程序或具有独立功能的代码段进行测试的过程&#xff1b; 2&#xff09;集成测试&#xff1a;是在单元测试的基础上&#xff0c;先通过单元模块…...

前端常用终端各种命令

前端常用终端各种命令 之前有小伙伴们留言说&#xff0c;想要些常见的操作终端的命令&#xff0c;今天就给大家整理了份很全很全的命令指南 1. Linux版本 a. 内核版本格式 xx.yy.zz&#xff1a; xx主版本、yy次版本、zz末版本小于2.6版本&#xff1a;次版本奇数为开发版、次…...

人家这才叫软件测试工程师,你那只是混口饭吃(附HR面试宝典)

前些天和大学室友小聚了一下&#xff0c;喝酒喝大发了&#xff0c;谈天谈地谈人生理想&#xff0c;也谈到了我们各自的发展&#xff0c;感触颇多。曾经找工作我迷茫过、徘徊不&#xff0c;毕业那会我屡屡面试失败&#xff0c;处处碰壁&#xff1b;工作两年后我一度想要升职加薪…...

在腾讯做了4年软件测试,来面试要求35k,让我见识到了真正的软件测试天花板...

人人都有大厂梦&#xff0c;对于程序员来说&#xff0c;BAT 为首的一线互联网公司肯定是自己的心仪对象&#xff0c;毕竟能到这些大厂工作&#xff0c;不仅薪资高待遇好&#xff0c;而且能力技术都能够得到提升&#xff0c;最关键的是还能够给自己镀上一层金&#xff0c;让人瞻…...

哥们别逗 了,写个脚本那真不叫运维自动化!

哥们别逗 了&#xff0c;写个脚本那真不叫运维自动化!2014-12-16 http://3060674.blog.51cto.com/3050674/1590803 好久没写文章了&#xff0c;最近要来刷下存在感&#xff0c;近两 年&#xff0c;运维自动化被炒的火的不行&#xff0c;行业趋势不可挡&#xff0c;现在企业招运…...

Selenium2自动化测试实战基于Python语言》读书笔记--第1章

第1章 自动化测试基础 1.1 软件测试分类 根据项目流程阶段划分软件测试 1&#xff09; 单元测试&#xff1a;又称模块测试&#xff0c;是对程序中的单个子程序或具有独立功能的代码段进行测试的过程&#xff1b; 2&#xff09;集成测试&#xff1a;是在单元测试的基础上&am…...

2022年,真的是测试行情不好吗?

关于今年的就业市场&#xff0c;很多人表示特别惨淡&#xff0c;以往简历一投就有大批企业来联系&#xff0c;今年自己投递一大堆简历出去&#xff0c;可能全部都是已读不回&#xff0c;或者只有寥寥几家面试邀约。 这是不是正在找工作的你&#xff0c;所遇到的情况呢&#xf…...

这些软件测试面试题如果都会,月薪最少20k+【内附面试宝典】

导读 刚好最近休息了一下&#xff0c;顺便整理了一些软件测试岗面试题&#xff0c;现在就把整理的面试题分享给大家&#xff0c;希望可以帮助到各位&#xff0c;废话就不多说了直接上干货。 Tip&#xff1a;我整理的面试题都按照这个目录&#xff0c;点击标题阅读即可&#x…...

前端自动化构建工具:用Gulp4.0搭建一个基本的前端开发环境

一个项目的完成一般需要经过三个步骤&#xff1a;初始化、开发和部署。在前端开发过程中&#xff0c;我们经常需要依靠一些自动化构建工具来优化前端工作流程&#xff0c;来帮助我们完成一系列繁琐的工作&#xff0c;例如浏览器热更新、ES6编译、代码压缩、添加样式前缀、图片压…...

入行软件测试5年,跳槽3次,我摸透了软件测试这一行

软件测试是一个付出就有回报的工作&#xff0c;可能很多人会说软件测试就是吃青春饭&#xff0c;然而其他工作又何尝不是&#xff1f;没有哪一家公司养尸位素餐之人&#xff0c;大龄员工有被辞退的&#xff0c;也有没被辞退的。干任何职业&#xff0c;抱着一劳永逸的心态&#…...

软件测试岗位未来趋势怎么样?

先说结论&#xff1a;软件测试的岗位不会越来越少&#xff0c;但是要求会越来越高。 岗位少不可怕&#xff0c;要求越来越高也不可怕&#xff0c;可怕的是&#xff0c;软件测试行业已经发生巨变&#xff0c;而你却原地踏步&#xff01; 很多刚刚进入这个行业的同学&#xff0…...

测试基础面试相关

http的工作过程 客户端发起请求 通过dns解析域名&#xff0c;获取ip地址 向ip地址服务器发送http请求 与服务器建立tcp&#xff08;三次握手&#xff09;连接 服务器响应http请求 浏览器解析html代码&#xff0c;并请求代码中的资源 浏览器对页面进行渲染呈现给客户 tcp和udp…...

毕业进入HW,从测试工程师到项目经理,现如今在鹅厂年收入百万,我的给大家的一些建议...

有许多的朋友问我&#xff1a;软件测试行业到底有没有前景和出路&#xff1f; 这个问题我还是很有发言权的&#xff0c;现35&#xff0c;年收入百万 先说一下我的工作路径&#xff1a;毕业进入HW&#xff0c;研发测试岗&#xff0c;从测试工程师&#xff0c;到测试经理&#…...

《Selenium2自动化测试实战基于Python语言》读书笔记--第1章

第1章 自动化测试基础 1.1 软件测试分类 根据项目流程阶段划分软件测试 1&#xff09; 单元测试&#xff1a;又称模块测试&#xff0c;是对程序中的单个子程序或具有独立功能的代码段进行测试的过程&#xff1b; 2&#xff09;集成测试&#xff1a;是在单元测试的基础上&am…...

那些一门心思研究自动化测试的人,最后都怎样了?

很多人对功能测试是有误区的。以为功能测试是一个软件测试岗位的初级&#xff0c;等到做时间长了就自然而然成为高级了。遗憾的是&#xff0c;功能测试并不会随着职场年龄变得更高级。 这时&#xff0c;有人意识到不能总是当点工&#xff0c;想学习新的技术&#xff0c;不过&a…...

数据驱动的教育过程关键在于个人认知模式的数字刻画

在现代信息社会中&#xff0c;终身学习已成为一种必然&#xff0c;每个人都面临学习与被学习&#xff0c;因此&#xff0c;本文中涉及到的教师与学生的角色不特定限定在于教育活动中的职业描述&#xff0c;而由具体行为的需求和表达去设定。 目前所面临的现实困难&#xff1a;…...