luogu解题报告:P1186玛丽卡【图论/最短路/堆优化dijkstra】_luogu p1186-程序员宅基地

技术标签: 算法  线段树  ---图论---  基础图算法-最短路/bst/连通性  ---数据结构---  dijkstra  

题目见https://www.luogu.org/problem/show?pid=1186

分析

一个简单的思路是枚举删除每一条边,然后跑堆优化dijkstra算法。但这样的复杂度恐怕过大。因此有一个简单的优化思路:第一次跑dijkstra时记录路径上的点。显然,堵车的路一定处于这些点之间,因为如果不是,玛丽卡走原先的最短路一定最短。因此只需要枚举删除处于最短路上的点之间的边,再跑堆优化dijkstra即可。代码使用zkw树优化。

示例代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

// basic of graph
struct p {
    int to, next, dis;
}edge[3000000];
int head[1005], top = 0;
void push(int i, int j, int k)
{
    edge[++top].to = j;
    edge[top].dis  = k;
    edge[top].next = head[i];
    head[i] = top;
}

// a heap

class zkw_tree {
    int dat[2050];
    int from[2050];
    int n;
    public:
        zkw_tree()
        {
            memset(dat, 127/3, sizeof dat);
            for (int i = 1; i < 2050; i++)
                from[i] = i-n+1;
        }
        void clear()
        {
            memset(dat, 127/3, sizeof dat);
            for (int i = 1; i < 2050; i++)
                from[i] = i-n+1;
        }
        void init(int num)
        {
            n = num;
        }
        void modify(int i, int new_val)
        {
            dat[i+n-1] = new_val;
            for (int pos = (i+n-1)>>1; pos; pos>>=1) {
                int lft = pos<<1, rgt = (pos<<1)+1;
                if (dat[lft] <= dat[rgt]) {
                    dat[pos] = dat[lft];
                    from[pos] = from[lft];
                } else {
                    dat[pos] = dat[rgt];
                    from[pos] = from[rgt];
                }
            }
        }
        int query()
        {
            return from[1];
        }
        int top()
        {
            return dat[1];
        }
}zkw_heap;

// some var & func
int forbid_s = 0, forbid_t = 0;
int n, m;
bool eq(int a, int b, int c, int d)
{
    return (a == c && b == d) || (a == d && b == c);
}

// dijkstra
int dis[1005], pre[1005];
int dijkstra(bool take_path = false)
{
    memset(dis, 127/3, sizeof dis);
    dis[1] = 0;
    zkw_heap.clear();
    zkw_heap.modify(1, 0);
    for (int i = 1; i < n; i++) {
        int k = zkw_heap.query();
        dis[k] = zkw_heap.top(); zkw_heap.modify(k, 233333333);
        //cout << k << " " << dis[k] << endl;
        if (k == n) break;
        for (int j = head[k]; j; j = edge[j].next) {
            int to = edge[j].to, d = edge[j].dis;
            if (dis[to] > dis[k]+d && !eq(k, to, forbid_s, forbid_t)) {
                dis[to] = dis[k]+d;
                if (take_path)
                    pre[to] = k;
                zkw_heap.modify(to, dis[to]);
            }
        }
    }
    return dis[n];
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/OIljt12138/article/details/52903752

智能推荐

2021SC@SDUSC 山大智云 1.综述_sdcus-程序员宅基地

文章浏览阅读377次。2021SC@SDUSC 山大智云 1.综述2021SC@SDUSC0.项目简介"山大智云"是以网盘功能为基础的在线应用系统。以seafile开源版本为基础,拓展网盘的应用功能和场景化的业务适配。该项目已事先校园统一认证,文件锁,在线编辑预览,全文搜索,文件病毒扫描,审计,离线上传等功能。1.项目配置1.0 安装Ubuntu18.041.1 安装Dockerapt install docker.server1.2 创建Docker容器docker run -it -p 8000:800_sdcus

fdisk 分区及格式化-程序员宅基地

文章浏览阅读251次。# 对分区sdb操作, m 帮助fdisk /dev/sdb建好分区,格式化文件系统:挂载:mount /dev/sdb4 /3转载于:https://www.cnblogs.com/listenerln/p/7388655.html_fdisk可以格式化分区吗

bunsenlasb中文Linux,在线试用 200 多种 Linux 和 Unix 操作系统-程序员宅基地

文章浏览阅读178次。只要打开该网站,选择你需要的 Linux/Unix 发行版,然后开始试用!-- Sk(作者)不久前我们介绍过 OSBoxes ,该网站提供了一系列免费且开箱即用的 Linux 和 Unix 虚拟机。你可以在你的 Linux 系统中下载这些虚拟机并用 VirtualBox 或 VMWare workstation 试用。今天,我偶然发现一个名叫 “DistroTest” 的类似服务。与 OSBoxe..._bunsenlabs

Linux芯片级移植与底层驱动(基于3.7.4内核) --中断控制器_cpsid if-程序员宅基地

文章浏览阅读327次。3. 中断控制器驱动在Linux内核中,各个设备驱动可以简单地调用request_irq()、 enable_irq()、disable_irq()、local_irq_disable()、local_irq_enable()等通用API完 成中断申请、使能、禁止等功能。在将Linux移植到新的SoC时,芯片供应商需要提供该部分API的底层支持。local_irq_disabl_cpsid if

从10万到百亿营收的背后 | 同程旅游CTO V课堂实录_ctov;-程序员宅基地

文章浏览阅读2.7k次。转载酷饭网 http://qoofan.com/read/RnMkBREqGD.html前言在 10 多年的同程创业历程中,张海龙经历了从 5 人到万人的扩张、融资等过程,他对电子商务、O2O、在线旅游、创业历程、文化打造、技术团队提升等也有较深的理解和心得。作为同程旅游联合创始人暨现任CTO,张海龙全面负责着同程网一千多人的研发团队管理及同程研发中心的_ctov;

我看不懂,但我大受震撼!-程序员宅基地

文章浏览阅读235次。大家好,我是极客重生,9月开始了,又到了看书的季节。经典的书籍不在乎多,而在乎认真读完,领悟作者(大师)的真谛,经典书,就是值得反复阅读的书,每次阅读都可以获得新的认知!看一看有没有你喜欢..._linux操作系统知识地图2.0 pdf

随便推点

tomcat的classpath设置_tomcat配置classpath-程序员宅基地

文章浏览阅读560次。在tomcat启动的时候,tomcat不会用JDK的classpath,这个是在tomcat启动的catalina.sh里面设置的。如果需要把自己的目录加进去的话,在下面加一句。CLASSPATH:自己的目录。_tomcat配置classpath

DNS主从服务器详细配置_主dns和从dns怎么设置-程序员宅基地

文章浏览阅读517次。DNS域名的分层结构:根域 国家域 顶级域 二级域 主机名DNS解析过程:DNS的解析过程是分层解析的,一般客户机将解析的请求发送给它的DNS服务器,DNS服务器首先是从根DNS服务器开始改进域名解析请求,根将com域的IP反馈给客户机的本地DNS服务器,本地DNS服务器访问com域服务器,com域服务器反馈baidu域的IP给本地DNS服务器,本地DNS服务器访问baidu域服务器询问WWW域服务器的IP,baidu域服务器给DNS服务器反馈www域的ip,这时本地DNS服务器得到www.baid_主dns和从dns怎么设置

栈实现综合计算器(中缀表达式)_栈计算器中缀-程序员宅基地

文章浏览阅读123次。代码实现package com.springboot.数据结构.stack;/** * @author: 牧羊 * @Date: 2020/4/29 15:28 * 栈实现综合计算器(中缀表达式) */public class Calculator { public static void main(String[] args) { String..._栈计算器中缀

Qt-装饰者模式_qt装饰模式-程序员宅基地

文章浏览阅读1.1k次,点赞2次,收藏4次。1. 定义装饰者模式 装饰者模式动态地将责任附加到对象上。若要扩展功能,装饰者提供了比继承更有弹性的替代方案。装饰者和被装饰对象有共同的超类型你可以用一个或多个装饰者包装一个对象。既然装饰者和被装饰对象有相同的类型,所以在任何需要原始对象(被包装)的场合,可以用装饰过的对象代替它。装饰者可以在所委托被装饰者的行为之前与/或之后,加上自己的行为,以达到特定的目的。对象可以在任_qt装饰模式

how2j学习日志——J2EE(2018年3月28日)-程序员宅基地

文章浏览阅读152次。1.开始跟着站长学习J2EE,首页是简单的Tomcat安装和部署,我从官网上下载的是7.0.85版本,修改server.xml中的默认端口号为80。80端口是web服务的默认端口,因此在浏览器上输入127.0.0.1就行了,不需要再输入端口号。2.由于我把之前的继承包WampServer卸载了,因此去官网上重新下载了一个MySql服务器,版本是5.1.38(64位)。选择cu..._howj2ee

面向对象的三大特征_面向对象的三大特性-程序员宅基地

文章浏览阅读9.8k次,点赞5次,收藏37次。面向对象的三大特征——封装、继承、多态_面向对象的三大特性