洛谷 [P2886] 牛继电器Cow Relays_aiwa6731的博客-程序员宝宝

最短路 + 矩阵快速幂

我们可以改进矩阵快速幂,使得它适合本题
用图的邻接矩阵和快速幂实现
注意 dis[i][i] 不能置为 0

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
struct edge{
    int u, v, dis;
}e[10000];
int n, m, p, ss, tt;
void work() {
    int sub[10005];
    for(int i = 1; i <= m; i++) {
        cin >> e[i].dis >> e[i].u >> e[i].v;
        sub[++n] = e[i].u;
        sub[++n] = e[i].v;
    }
    sort(sub + 1, sub + n + 1);
    n = unique(sub + 1, sub + n + 1) - sub - 1;
    for(int i = 1; i <= m; i++) {
        e[i].u = lower_bound(sub + 1, sub + n + 1, e[i].u) - sub;
        e[i].v = lower_bound(sub + 1, sub + n + 1, e[i].v) - sub; 
    }
    ss = lower_bound(sub + 1, sub + n + 1, ss) - sub;
    tt = lower_bound(sub + 1, sub + n + 1, tt) - sub;
}
struct Matrix{
    int num[205][205];
    void clear() {
        memset(num, 0x3f, sizeof(num));
    }
    void unit() {
        memset(num, 0, sizeof(num));
        for(int i = 0; i < 205; i++) num[i][i] = 1;
    }
    Matrix operator * (const Matrix & b) {
        Matrix ans;
        ans.clear();
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                for(int k = 1; k <= n; k++) {
                    ans.num[i][j] = min(ans.num[i][j], num[i][k] + b.num[k][j]);
                }
            }
        }
        return ans;
    }
    void print() {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                printf("%d ", num[i][j]);
            }
            printf("\n");
        }
    }
    Matrix operator ^ (int k) {
        Matrix ans;
        k--;
        ans = (*this);
        while(k) {
            if(k & 1) ans = ans * (*this);
            (*this) = (*this) * (*this);
            k >>= 1;
        }
        return ans;
    }
};
int main() {
    cin >> p >> m >> ss >> tt;
    work();
    Matrix a;
    a.clear();
    //for(int i = 1; i <= n; i++) a.num[i][i] = 0;
    for(int i = 1; i <= m; i++) {
        a.num[e[i].u][e[i].v] = a.num[e[i].v][e[i].u] = min(e[i].dis, a.num[e[i].u][e[i].v]);
    }
    a = a ^ p;
    //a.print();
    printf("%d\n", a.num[ss][tt]);
    return 0;
}

转载于:https://www.cnblogs.com/Mr-WolframsMgcBox/p/8665828.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/aiwa6731/article/details/101349686

智能推荐

大数据开发的四个维度_IT时代周刊的博客-程序员宝宝_大数据的维度

大数据词已经无处不在,然而,其概念仍然存在混淆。大数据已被用于承载所有类型的概念,包括:巨量的数据、社交媒体分析、下一代数据管理能力、实时数据等。无论是任何种类,企业都已经开始理解并且探索如何以新的方式处理并分析大量的信息。这样,数量较少但不断增加的先驱者实现了突破性的业务成果。在对大数据的混淆中,很大一部分从大数据的定义开始。为了了解我们的调研受访者对该术语的定义,我们让每个受访者选出大数据的两...

读写文件并填写行号_读写文本文件并添加行号_weixin_45881103的博客-程序员宝宝

适 用 专 业适用于所有专业。实 验 目 的(1)熟练掌握内置函数open()的用法。(2)熟练运用内置函数len()、max()、enumerate()。(3)熟练运用字符串的strip()、just()和其他方法。(4)熟练运用列表推导式。实 验 内 容编写一个程序demo.py,要求运行该程序后,生成demo_new.py文件,其中内容与demo.py一样,只是在每一行的后面加上行号。要求行号以#开始,并且所有行的#垂直对齐。代码filename = 'demo.py'with

HTTP状态500 - java.lang.ClassNotFoundException:org.apache.jsp.index_jsp_追0逐的博客-程序员宝宝

HTTP Status 500 - java.lang.ClassNotFoundException: org.apache.jsp.index_jsptypeException reportmessagejava.lang.ClassNotFoundException: org.apache.jsp.index_jspdescriptionThe server encounte...

router vue 动态改变url_vue: router-link 动态路由_weixin_39713317的博客-程序员宝宝

动态路由:根据路由的不同请求不同的数据。$router 获取vue-router实例$route 获取url的详细信息:id表示在user后任意参数都可以访问到对应组件,但是必须有" / "。如: localhost:8080/user/1// router.js文件import Vue from 'vue'import Router from 'vue-router'import Home fr...

Android -- GreenDao3.2的简单使用_weixin_34248487的博客-程序员宝宝

1,最近看了一篇文章关于GreenDao的文章 ,感觉使用这个操作数据库还是很好用的,帮我们省了不少的查询代码,今天就和大家一起来简单的使用一下吧。首先这是官网地址:https://github.com/greenrobot/greendao,我们来按照文档一点点的来写一下2,首先要认识一下GreenDao是使用ORM(Object RelationShop Mapping)对象关系映射,就是...

码农分为两类:看过《数学之美》的与没看过的_程序猿阿诺的博客-程序员宝宝

引言《数学之美》这本书从第一版到目前最新的第三版,累计销量已愈百万册。这本书对于码农们来说,其重要性怎么强调都不为过。就说不管哪个“码农必读书单”吧,《数学之美》是必在其中的,甚至都在前三之内。对于视数学如洪水猛兽的人来说,看见一本书的书名里有“数学”二字,恐怕拿起它翻开封面的勇气都没有。但《数学之美》其实相当通俗易懂,甚至这才是它能够如此畅销的原因。这并不是一本讲述纯数学理论的书,它以一种深入浅出的方式,讲述了计算机科学领域中的经典问题与解决方法。看过的码农们应该拿起第三版再刷一遍,没看过的码农们

随便推点

ssh的密码登录和公钥登录_程序员八一的博客-程序员宝宝_ssh 密码

一.简述sshssh是加密的远程登录和远程执行命令的工具,它不仅在密码进行加密,对登录后执行的命令也进行了加密,所以比较安全,在这之前使用的是telent和R系列的命令,这些是明文传输,很不安全.一般的linux发行版本都带了ssh,不要手动安装.二.密码登录1.工作原理1.客户端向服务端发起登录请求,服务端返回公钥2.客户端用公钥加密自己的认证信息,发送到服务端3.服务端用私钥解密客户端发来的认证信息,匹配则登录成功,否则失败2.登录命令ssh 用户名@主机ip或者hostname

c++(基础)————模板(函数模板与类模板)_djh971102的博客-程序员宝宝

一、模板是干什么的?比如实现一个简单的比较大小的函数,如果要比较int、double、char等多种类型的数据,那么有多少中数据类型,我们就得实现多少个比较函数,然而这些函数除了类型不同之外,其他代码都是一样的(也就是代码实现的功能都相同,只是类型不同)。所以为了解决这种问题,我们就引入了模板,模板就是为了代码重用而生的二、函数模板:函数模板提供了一种函数行为,该函数行为可以用多种不同的类型...

细说 Java NIO_pecuyu的博客-程序员宝宝

前言:本篇主要用于梳理NIO的相关知识,诸如缓冲区、通道、文件锁、选择器,附带的会说一下IO的知识,因为在某些地方NIO会用到它们。鉴于NIO已经出来甚久,本文旨在总结知识与交流学习,同时若能给他人带来一点帮助,那也是一份意外收获。1、IO (java.io.*)在前面的两篇博客Java之IO流—字节流、Java之IO流—字符流,我们详细的梳理了字节流与字符流的体系与使用细节,并没有对他们两者做一个

ANT DESIGN VUE model 对话框标题改造_渣渣灰飞的博客-程序员宝宝

一、需求:给对话框标题处,加除标题之外的提示信息二、开始改造:1、改造好的示例2、官方文档提示:详细地址:Ant Design Vue3、代码: &lt;a-modal v-model="visible" :maskClosable="false" width="900px" &gt; //通过插槽设置标题 &lt;template slot="title"&gt;...

linux监控网络的指标,linux 各项监控指标小记_卜仆的博客-程序员宝宝

linux 指标监控小记自开始负责生产环境部署,中间遇到了若干线上环境内存以及CPU的问题。由于微服务以及容器的流行,现在已经可以很方便的使用 K8s + prometheus + grafana + alert 的方式进行监控,这足以覆盖大部分场景。最重要的事情已经交由最适合的组件去做,然而了解一些在裸机上的命令以及指标也是必不可少的:了解监控什么指标平时写一些脚本也经常会 OOM 或者 CPU...

cocos2dx spine动画反转_centor的博客-程序员宝宝_spine反转

SkeletonAnimation *m_pSpine= SkeletonAnimation::createWithJsonFile("spinefile.json", "spinefile.atlas", 1.0F); //m_pSpineBrow-&gt;setSkin("skinname1"); //auto slot = spSkeleton_findSlot(m_pSpineBrow-&gt;getSkeleton(), "slotnamne1"); //auto slot1 = spSk.

推荐文章

热门文章

相关标签