技术标签： spfa
这题就是个暴力spfa。。。
我们就从节点1开始更新，每次更新一圈。
我们可以发现，每个完全子图暴力扫过以后就不需要再扫了（因为不会再优），所以就可以过了（判一判是否扫过就可以了）。
这题有个重构图的解法。就是对于每个完全子图构建成一个菊花图，而边权便是1/2，然后跑一遍spfa就可以了。
#include<cstdio>
#include<cstring>
#define N 100010
using namespace std;
struct node{
int v,fr;}e[1000010];
int n,K,m,tail[N],cnt=0,a[1010][1010];
int f[N<<2],l=0,r=1,nr,d[N],tot=1;
bool bz[N],bz1[N];
inline int read()
{
int x=0; char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
void add(int u,int v) {
e[++cnt]=(node){
v,tail[u]}; tail[u]=cnt;}
int main()
{
freopen("spfa.in","r",stdin);
// freopen("spfa.out","w",stdout);
n=read(),K=read(),m=read();
for (int i=1;i<=m;i++)
for (int j=1;j<=K;j++)
a[i][j]=read(),add(a[i][j],i);
f[1]=1,d[1]=1;
while (l<r)
{
nr=r;tot++;
while (l<r)
{
l++;
for (int p=tail[f[l]],v;p;p=e[p].fr)
{
v=e[p].v;
if (!bz[v])
{
for (int i=1;i<=K;i++)
if (!bz1[a[v][i]])
{
d[a[v][i]]=tot;
f[++nr]=a[v][i];
bz1[a[v][i]]=1;
}
bz[v]=1;
}
}
}
r=nr;
if (bz1[n]) break;
}
if (!bz1[n]) puts("-1");
else printf("%d\n",d[n]);
return 0;
}
文章浏览阅读4.4k次，点赞2次，收藏4次。创建build.rs //build.rsexterncratedunce;usestd::{env,path::PathBuf};fnmain(){letlibrary_name="r2c";letroot=PathBuf::from(env::var_os("CARGO_MANIFEST_DIR").unwrap());..._rustc-link-lib
文章浏览阅读3.1k次，点赞4次，收藏34次。“数据可视化过程中，经常遇到两种不同类型图表组合的情况，就是所谓的双坐标轴组合图。最近学习中遇到了此问题，特学习和大家分享，部分内容有个人改进哟”01—效果图02—twoord.plot用法和参数解释---plotrix包# 1、用法/Usage：twoord.plot(lx,ly,rx,ry,data=NULL,main="",xlim=NULL..._r语言如何置组合图的横坐标标题和纵坐标标题
文章浏览阅读1.7k次。一. 将.proto 文件编译出java文件1.下载对应系统的protoc；【自用链接：https://pan.baidu.com/s/1yTwRi8CzvnjX9ICRExQpqQ 密码：mrow】2.在proto.exe所在文件目录下打开命令行（shift+右键），执行： protoc -I=E:\tmp --java_out=./ E:\tmp\send_mail...._proto: file does not reside within any path specified using
文章浏览阅读1.5k次。一、引入Hive原因– 对存在HDFS上的文件或HBase中的表进行查询时，要手工写一堆MapReduce代码– 对于统计任务，只能由懂MapReduce的程序员才能搞定，耗时耗力FaceBook实现并开源Hive，解决海量结构化日志查询– Hive是一个SQL解析引擎，将SQL语句转译成MR Job，然后在Hadoop平台上运行，达到快速开发的目的。Hive一般不会直接接入到业务中使用，从某种意..._hive-jdbc:pom:1.1.0-cdh5.13.0 mvn
文章浏览阅读589次。课程目标Window系统下的环境搭建，go的环境配置，MinGW的环境配置Linux系统下的环境搭建，go的环境配置，Linux自带gcc很方便摘要在macOS和Linux下gcc，在window下需要安装MinGW。同时需要保证环境变量CGO_ENABLED被设置为1，这是表示cgo是否被启用状态。在本地构建时CGO_ENABLED默认启用，在交叉构建cgo是默认禁用的。比如交叉构建ARM环境运..._golang cgo 环境变量
文章浏览阅读4.3k次。使用自定义日志配置日志多环境配置.https://docs.spring.io/spring-boot/docs/current/reference/htmlsingle/#boot-features-custom-log-levelslogging.config 指定自定义logback-xxx.xml配置文件,不要使用logback-spring.xml,因为会出现logPath_IS_U..._log4j project.artifactid_is_undefined
文章浏览阅读547次。java反序列化_shiro550反序列化
文章浏览阅读1.7w次，点赞6次，收藏13次。原始数据：id scoreaaa 1aaa 2aaa 3预期结果：id scoreaaa 1,2,3可使用select id,concat_ws(',',collect_set(cast(colname as string))) from table;使用concat_ws函数，需将字段转成string格式，collect_set会对该..._concat_ws 去重
文章浏览阅读8.6k次。1.npm 安装依赖npm install --save @riophae/vue-treeselect2. 在需要使用的组件中引入import Treeselect from '@riophae/vue-treeselect'import '@riophae/vue-treeselect/dist/vue-treeselect.css' components: { Tre..._vue-treeselect 属性
文章浏览阅读224次。计算机毕业设计Java高校后勤保修系统（源码+系统+mysql数据库+lw文档）ssm基于uniapp+Vue框架的《露营》App开发与实现。springboot基于springboot的社会公益平台。ssm基于HTML的“牧经校园疫情防控网站”的设计与实现。springboot基于Java的高校教室申请管理系统。JSP客户关系管理系统的设计与实现sqlserver。JSP教学视频点播系统的设计与实现SQLServer。ssm基于HTML的“守护萌宠”网站的设计与实现。_保修系统系统包图
文章浏览阅读2.5k次。1.先在Git中仓库建立可在github中或码云中搭建 或自己搭建服务器注意设置忽略上传的文件 过滤掉一些文件或文件夹，那么被过滤的内容就不会被git管理，比如： build/： 过滤整个build文件夹； *.class： 过滤所有.class后缀的文件； path/to/local.properties: 过滤具体文件 .gi..._使用 git的注意事项
文章浏览阅读1w次，点赞2次，收藏15次。学习Spring Web Flow的简单使用_spring flow