[ABC218F] Blocked Roads 题解

news/2024/4/15 15:10:19

首先很多人时间复杂度估算错了,这里,我们设 m = n 2 m=n^2 m=n2,这是最坏的情况,所以单次 BFS 的时间复杂度是 O ( n + m ) O(n+m) O(n+m) O ( n 2 ) O(n^2) O(n2) 级别的。

每条边都跑一次就是 O ( n 4 ) O(n^4) O(n4) 了,所以会时超。

我们的做法是把原图最短路的边记录下来,然后删了原图的边再跑最短路,否则直接输出原答案。

因为最短路不大于 n n n,因此时间复杂度是 O ( n 3 ) O(n^3) O(n3) 级别的,可以通过。

#include<bits/stdc++.h>
#define LL int
using namespace std;
const LL N=405;
struct node
{LL to,num;
};
vector<node>v[N],v2[N];
LL n,m,x,y,pos,dis[N],nxt[N],c[N*N],ans,in[N];
pair<LL,LL>lst[N];
queue<LL>q;
LL work(LL pos)
{for(int i=0;i<=n;i++){dis[i]=1e9;}dis[1]=0;while(!q.empty())q.pop();q.push(1);while(!q.empty()){LL t=q.front();q.pop();for(auto j:v[t]){if(j.num==pos)continue;if(dis[j.to]>dis[t]+1){dis[j.to]=dis[t]+1;if(pos==0)lst[j.to]={t,j.num};q.push(j.to);}if(j.to==n)return dis[n];}}	if(dis[n]==dis[0])return -1;
}
void dg(LL x)
{while(x>1){in[lst[x].second]=1;x=lst[x].first;		}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);v[x].push_back({y,i});}ans=work(0);dg(n);if(dis[n]==dis[0])ans=-1;else ans=dis[n];for(int i=1;i<=m;i++){if(!in[i]){printf("%d\n",ans);continue;}printf("%d\n",work(i));}return 0;
}

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

相关文章

云存储--1

背景 这一板块主要是讲诉云计算中的存储板块。 那么云存储主要分为三大类&#xff1a;块存储、文件存储、对象存储。 那么&#xff0c;这一章我们来了解一下什么是块存储&#xff0c;以及块存储在云计算当中的使用场景。 1、 什么是块存储&#xff1f; 我们来思考一个场景&a…

自建存储服务器与网盘的比较

作为单位的网管,对ftp等自建存储服务并不陌生,最近发展得如火如荼的云存储自然也不能视而不见.经过一番试用和了解,个人觉得现在已经是和自建局域网存储说再见的时候了. 自建局域网存储不外乎是ftp和网络共享等.在局域网内放置一台存储服务器,开好ftp或者网络共享,新建一堆用户…

中创存储|想要一个好用的分布式存储云盘,到底该怎么选

隐私、数据、权利、审查、身份……这都是存储用户最关心的问题。 针对传统互联网的中心化运行、数据被互联网巨头垄断、运营商需要为各种成本买单等问题。 存储市场需要全新的技术来颠覆如今的互联网巨头垄断局面&#xff0c;保护每一个互联网用户的利益&#xff0c;简单来说…

阿里云OSS,搭建自己的云储存

目前&#xff0c;对于互联网的疯狂发展&#xff0c;数据储存成为了大多数个人或小公司的瓶颈。由于服务器的磁盘空间不是很大、宽带也不是很充足。储存网站的内容成为了一笔较大的开销。尤其是有下载、视频、音乐等业务的网站来说&#xff0c;那更是一笔庞大的开销。 较比之前…

自建OSS存储

安装oss存储服务 minio官方文档 #获取minio wget https://dl.min.io/server/minio/release/linux-amd64/minio#加权限 chmod x minio#后台启动minio ./minio可以换成minio的绝对路径 --address是服务地址 #--console-address是控制台地址&#xff0c;可以通过web进行访问 记得…

阿里云-云存储OSS

1.简述OSS 数据的可靠性较强&#xff1a;三重备份 系统的安全性较强&#xff1a;对称加密&#xff0c;签名权限控制以及防盗链功能&#xff1b; 文件存储的容量无限&#xff1b; 无需人工运维&#xff1b; 部署扩容&#xff1a;无需规则&#xff0c;按需扩容&#xff1b; 提供…

阿里云国际站的对象存储oss与自建存储的区别

对象存储oss是阿里云国际站的一个云产品&#xff0c;其功能是提供海量、安全可靠、低成本高持久的云存储服务。那么为什么要选择阿里云国际站的对象存储oss而不是自建存储&#xff0c;下面跟Unirech小编从几个方面来对比分析&#xff1a; 1.持久稳定性 阿里云作为国际大厂商…

文件存储解决方案-云存储阿里 OSS

文件存储解决方案-云存储阿里 OSS 1.文件存储&#xff08;上传&#xff09;解决方案讨论 1.图解 文件存储解决方案-云存储阿里 OSS 解读上图 普通上传并不是分布式&#xff0c;也不是集群&#xff0c;可用性不高普通上传的分布式情况&#xff0c;使用了集群&#xff0c;但是…

如何自建云存储平台?

云存储盛行的今天,IT专家需要用比以往更加宽广的视野来审视他们的数据中心,云计算,云存储,大数据,这些概念和技术不但要关注,而且如何融入到自己的当前环境中是迫在眉睫的事情了。以往在组织内部独来独往的IT部门(比如网络和存储)现在由于融合的缘故必须更加紧密地互相配…

搭建私有云存储

一、先废话一下 进入4G时代以来&#xff0c;用户数据已进入快速发展阶段&#xff0c;数据越来越多&#xff0c;无论是日常工作文件还是照片&#xff0c;视频和文件&#xff0c;数据都越来越大&#xff0c;4G时代的到来便于我们的备份&#xff0c;对于每日数据&#xff0c;我们…

我是如何打造出自己私有云存储的

今天给大家分享下我的NAS搭建方案&#xff0c;去年双十一的时候入手了一套NAS设备&#xff0c;用了几个月时间&#xff0c;好用是好用&#xff0c;但确实还没发挥出其价值&#xff0c;目前它最大的功能就是给我的mac做time-machine备份&#xff0c;要是没这个备份的话&#xff…

如何简单快速搭建自己的云对象存储服务(OSS)

简单来说&#xff0c;其实我们只需要有一台服务器&#xff0c;利用服务器的各种资源&#xff0c;搭配其它厂商开发的软件&#xff0c;就能很轻易拥有自己的云对象存储服务。不需要在阿里云上花钱买什么服务&#xff0c;甚至还能自己给别人提供服务&#xff0c;真的是太爽了。 云…

Keil MDK 添加.c源文件 和.h头文件

1. keil uVision5 2. keil 版本 V5.22&#xff0c;之前用过V538 的版本&#xff0c;538版本的有语法错误编译的时候也不会报&#xff0c;所以就换了V522 的版本 3. 把.c 文件复制到要添加的目录下&#xff0c;在keil工程中添加 test.c 源文件&#xff0c;点击keil 软件的左上角…

【C语言】指针概要

文章目录 一、什么是指针二、指针类型三、野指针四、二级指针五、字符指针六、数组指针定义数组名 七、函数指针 一、什么是指针 指针就是地址&#xff0c;口语中说的指针通常指的是指针变量。我们可以通过&&#xff08;取地址操作符&#xff09;取出变量的内存起始地址&a…

Android面试题及答案3

Java Android面试题 JAVA相关基础知识 1、面向对象的特征有哪些方面 1.抽象&#xff1a; 抽象就是忽略一个主题中与当前目标无关的那些方面&#xff0c;以便更充分地注意与当前目标有关的方面。 抽象并不打算了解全部问题&#xff0c;而只是选择其中的一部分&#xff0c…

10年回顾:世界各地开发高手谈Java-Java基础-Java-编程开发

<script type"text/javascript"> google_ad_client "pub-8800625213955058"; /* 336x280, 创建于 07-11-21 */ google_ad_slot "0989131976"; google_ad_width 336; google_ad_height 280; // </script> <script type"t…

android 面试题(三)

JAVA相关基础知识 1、面向对象的特征有哪些方面 1.抽象&#xff1a; 抽象就是忽略一个主题中与当前目标无关的那些方面&#xff0c;以便更充分地注意与当前目标有关的方面。 抽象并不打算了解全部问题&#xff0c;而只是选择其中的一部分&#xff0c;暂时不用部分细节。抽…

RFT的对象识别技术

虽然目前在Watir的对象识别中(基于IEdev与Autoit)基本没有碰到识别问题,但该文章的介绍还是收获颇多,推荐! http://www.ibm.com/developerworks/cn/rational/r-cn-extendsrftobj/ 2008 年 2 月 28 日 长期困扰 Rational Functional Tester (RFT) 自动化测试的一个问题就是如何…

HTTP验证大法(Basic Auth,Session, JWT, Oauth, Openid)

成为一个"认证”老司机 本文翻译自Auth-Boss。 如果有翻译的不恰当或不对的地方&#xff0c; 欢迎指出。 成为一个认证老司机&#xff0c; 了解网络上不同的身份认证方法。 本文档的目的是记录和编目Web上的身份验证方法。认证指的是创建一个系统的过程&#xff0c;用户可…

传智博客(JavaWeb方面的所有知识)听课记录(经典)

一、 JavaWeb基础 第一天&#xff1a; 1&#xff0e;Eclipse详解&#xff1a; (1).Bad versionnumber in .class file&#xff1a;编译器版本和运行(JRE)版本不符合。高的JRE版本兼容低版本的编译器版本。 (2).当程序有错误的时候&#xff0c;使用Debug as 运行程序。双击…
最新文章