正文

洛谷 P5663 加工零件 & [NOIP2019普及组] （奇偶最短路）

IP云
IP云V管理员/4 阅读
11/29
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

传送门

解题思路

很容易想到用最短路来解决这一道问题（题解法），因为两个点之间可以互相无限走，所以如果到某个点的最短路是x，那么x+2，x+4也一定能够达到。

但是如何保证这是正确的呢？比如说到某个点的最短路是x，为什么不可能走一下弯路，是某一条路径的长度是x+1或者x+3或者x+5呢？

所以就用到了 奇偶最短路 。所谓奇偶最短路，就是对于每一个点，记录下走偶数步的最短路（ou[i]）和走奇数步的最短路（ji[i]），转移式为：

ji[v]=min(ou[u]+1,ji[v]);

ou[v]=min(ji[u]+1,ou[v]);

注意一定要用u去更新v，即距离近的去更新远的。

AC代码 
 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int n,m,Q;

 int ji[maxn],ou[maxn],vis[maxn],p[maxn];

 queue<int> q;

 struct edge{

     int v,next;

 }e[*maxn];

 int cnt;

 void insert(int u,int v){

     e[++cnt].v=v;

     e[cnt].next=p[u];

     p[u]=cnt;

 }

 int main(){

     memset(ji,0x3f,sizeof(ji));

     memset(ou,0x3f,sizeof(ou));

     memset(p,-,sizeof(p));

     cin>>n>>m>>Q;

     for(int i=;i<=m;i++){

         int u,v;

         scanf("%d%d",&u,&v);

         insert(u,v);

         insert(v,u);

     }

     ou[]=;

     q.push();

     while(!q.empty()){

         int u=q.front();

         q.pop();

         vis[u]=;

         for(int i=p[u];i!=-;i=e[i].next){

             int v=e[i].v;

             if(ji[v]>ou[u]+){

                 ji[v]=ou[u]+;

                 if(vis[v]==){

                     q.push(v);

                     vis[v]=;

                 }

             }

             if(ou[v]>ji[u]+){

                 ou[v]=ji[u]+;

                 if(vis[v]==){

                     q.push(v);

                     vis[v]=;

                 }

             }

         }

     }

     for(int i=;i<=Q;i++){

         int a,l;

         scanf("%d%d",&a,&l);

         if(((l&)&&ji[a]<=l)||((!(l&))&&ou[a]<=l))printf("Yes\n");

         else printf("No\n");

     }

     return ;

 }

//CSP2019普及组 t4

洛谷 P5663 加工零件 & [NOIP2019普及组] （奇偶最短路）的更多相关文章
  1. 洛谷 P5660 数字游戏 & [NOIP2019普及组]

    传送门 洛谷改域名了QAQ 解题思路 没什么好说的,一道红题,本不想发这篇博客 ,但还是尊重一下CCF吧QAQ,怎么说也是第一年CSP呢! 用getchar一个个读入.判断.累加,最后输出即可. 不过 ...

  2. 洛谷 P5663 加工零件

    题目传送门 解题思路: 最暴力的做法: bfs模拟,每次将一个阶段的所有点拿出来,将其所有直连的点都放进队列,知道本阶段结束,最后看1号点会不会在最后一个阶段被放入队列.(洛谷数据40分) 优化了一下 ...

  3. 洛谷 P5661 公交换乘 & [NOIP2019普及组] （模拟）

    传送门 解题思路 先把所有的数据读下来. 对于地铁,答案直接加,然后把编号放入一个数组a内. 对于公交车,从前往后枚举a数组,然后找到出现最早的且符合价钱大于等于公交车的价钱,然后把这个数删除(变为0 ...

  4. 洛谷【P2669】NOIP2015普及组 T1金币

    我对模拟的理解:http://www.cnblogs.com/AKMer/p/9064018.html 题目传送门:https://www.luogu.org/problemnew/show/P266 ...

  5. 洛谷P1003 铺地毯 noip2011提高组day1T1

    洛谷P1003 铺地毯 noip2011提高组day1T1 洛谷原题 题目描述 为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯.一共有 n ...

  6. P5663 加工零件

    P5663 加工零件 题解 暴力搜索 搜索显然会TLE #include<iostream> #include<cstdio> #include<cstdlib> ...

  7. 洛谷P2832 行路难 分析+题解代码【玄学最短路】

    洛谷P2832 行路难 分析+题解代码[玄学最短路] 题目背景: 小X来到了山区,领略山林之乐.在他乐以忘忧之时,他突然发现,开学迫在眉睫 题目描述: 山区有n座山.山之间有m条羊肠小道,每条连接两座 ...

  8. 洛谷 P5662 纪念品 & [NOIP2019普及组] （dp，完全背包）

    传送门 解题思路 本题首先要明白,在每一天时,最优策略是先进行操作2(卖),再进行操作1(买),才能是利益最大化. 本题很显然当只有两天时,是一个完全背包,就是把当日价钱当做体积,把明日价格和今日价格 ...

  9. NOIP2017提高组Day1T3 逛公园 洛谷P3953 Tarjan 强连通缩点 SPFA 动态规划 最短路 拓扑序

    原文链接https://www.cnblogs.com/zhouzhendong/p/9258043.html 题目传送门 - 洛谷P3953 题目传送门 - Vijos P2030 题意 给定一个有 ...

随机推荐
  1. Node.js的url模块简介

    什么是URL URL是Uniform Location Resource的缩写,翻译为“统一资源定位符”,也就是描述资源位置的固定表示方法.被URL描述的资源可以位于互联网上,也可以位于本地. URL ...

  2. python – 如何禁用Django的CSRF验证？

    如果只需要一些视图不使用CSRF,可以使用@csrf_exempt: from django.views.decorators.csrf import csrf_exempt @csrf_exempt ...

  3. Codeforces Gym 100851 K King's Inspection ( 哈密顿回路 && 模拟 )

    题目链接 题意 : 给出 N 个点(最多 1e6 )和 M 条边 (最多 N + 20 条 )要你输出一条从 1 开始回到 1 的哈密顿回路路径,不存在则输出 " There is no r ...

  4. matlab中句柄@的用法

    @是Matlab中的句柄函数的标志符,即间接的函数调用方法. 1 句柄函数 主要有两种语法: handle = @functionname handle = @(arglist)anonymous_f ...

  5. (WCF) There is already a listener on IP endpoint 0.0.0.0:9999.

    有個nettcpbinding, service host總是不能起來,出現如題錯誤. 查了下,同樣的程序并沒有在進程裏面,但是看起來好像有其他的程序在占用這個Port C:\Program File ...

  6. Unity3D 中的FOV

    一直以为Unity中的相机FOV指的是frustum两个对角边的方向夹角,所以在看一篇教程的时候怎么算都算不对.后来灵机一动,查了一下,才发现Unity中的Fov指的是垂直方向的FOV: 参见这里:h ...

  7. [HNOI2015]菜肴制作贪心的证明

    [HNOI2015]菜肴制作贪心的证明 先吐槽一句为什么网上都没人证这个东西,我觉得一点也不显然啊... 判环不用说了,现在处理一个DAG.考虑按题意模拟:建反图(边从后选的点连向先选的点),每次找全 ...

  8. 同一个tomcat部署多个项目11

    在开发项目中,有时候我们需要在同一个tomcat中部署多个项目,小编之前也是遇到了这样的情况,碰过不少的壁,故整理总结如下,以供大家参考.(以Linux为例,其他系统同样适用) 一.首先将需要部署的项 ...

  9. 【Python】学习笔记九：面向对象拓展

    调用类的其他信息 在定义方法的时候,必须有self这一参数.这个参数表示某个对象,对象拥有类的所有性质.那么我们可以通过self,调用类属性 class people(object): action ...

  10. 前台ajax传数组，后台java接收

    后端 //添加 @RequestMapping(value = "checkChoise") @ResponseBody ResultJson checkChoise(@Reque ...

相关阅读

目录[+]