[LUOGU] P2886 [USACO07NOV]牛继电器Cow Relays

时间:2023-01-29 10:15:57

https://www.luogu.org/problemnew/show/P2886

给定无向连通图,求经过k条边,s到t的最短路

Floyd形式的矩阵乘法,同样满足结合律,所以可以进行快速幂。

离散化大可不必sort+unique,因为我们甚至并不在乎相对大小,只是要一个唯一编号,可以开一个桶记录

之所以进行k-1次快速幂,是因为邻接矩阵本身就走了一步了。

#include<iostream>
#include<cstring>
#include<cstdio> using namespace std; const int MAXN=; int k,m,s,t; int a[MAXN][MAXN];
int id[MAXN<<],tot; struct Mat{
int data[MAXN][MAXN];
Mat(int x=){memset(data,x,sizeof(data));}
Mat operator*(const Mat &rhs){
Mat ret(0x3f);
for(int k=;k<=tot;k++)
for(int i=;i<=tot;i++)
for(int j=;j<=tot;j++)
ret.data[i][j]=min(ret.data[i][j],data[i][k]+rhs.data[k][j]);
return ret;
}
Mat operator^(int x){
Mat ret;memcpy(ret.data,a,sizeof(a));
for(Mat base=*this;x;x>>=){
if(x&) ret=ret*base;
base=base*base;
}
return ret;
}
}; int main(){
memset(a,0x3f,sizeof(a));//
cin>>k>>m>>s>>t;
for(int i=;i<=m;i++){
int x,y,w;
cin>>w>>x>>y;
if(!id[x])id[x]=++tot;
if(!id[y])id[y]=++tot;
x=id[x];y=id[y];
a[x][y]=a[y][x]=w;
}
s=id[s];t=id[t];
Mat e;
memcpy(e.data,a,sizeof(a));
e=e^(k-);
cout<<e.data[s][t];
return ;
}

[LUOGU] P2886 [USACO07NOV]牛继电器Cow Relays的更多相关文章

  1. P2886 &lbrack;USACO07NOV&rsqb;牛继电器Cow Relays

    题目描述 For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race ...

  2. 洛谷P2886 &lbrack;USACO07NOV&rsqb;牛继电器Cow Relays

    题意很简单,给一张图,把基本的求起点到终点最短路改成求经过k条边的最短路. 求最短路常用的算法是dijkstra,SPFA,还有floyd. 考虑floyd的过程: c[i][j]=min(c[i][ ...

  3. Luogu 2886 &lbrack;USACO07NOV&rsqb;牛继电器Cow Relays

    BZOJ 1706权限题. 倍增$floyd$. 首先这道题有用的点最多只有$200$个,先离散化. 设$f_{p, i, j}$表示经过$2^p$条边从$i$到$j$的最短路,那么有转移$f_{p, ...

  4. 洛谷 P2886 &lbrack;USACO07NOV&rsqb;牛继电器Cow Relays

    题面 解题思路 ## floyd+矩阵快速幂,跟GhostCai爷打赌用不用离散化,最后完败..GhostCai真是tql ! 有个巧妙的方法就是将节点重新编号,因为与节点无关. 代码 #includ ...

  5. luogu题解 P2886 【牛继电器Cow Relays】-经过K边最短路&amp&semi;矩阵

    题目链接: https://www.luogu.org/problemnew/show/P2886 Update 6.16 最近看了下<算法导论>,惊奇地发现在在介绍\(APSP\) \( ...

  6. &lbrack;USACO07NOV&rsqb;牛继电器Cow Relays

    题目描述 给出一张无向连通图,求S到E经过k条边的最短路. 输入输出样例 输入样例#1: 2 6 6 4 11 4 6 4 4 8 8 4 9 6 6 8 2 6 9 3 8 9 输出样例#1: 10 ...

  7. &lbrack;USACO07NOV&rsqb;牛继电器Cow Relays &lpar;最短路&comma;DP&rpar;

    题目链接 Solution 非正解 似乎比较蛇啊,先个一个部分分做法,最短路+\(DP\). 在求最短路的堆或者队列中存储元素 \(dis_{i,j}\) 代表 \(i\) 这个节点,走了 \(j\) ...

  8. &lbrack;luoguP2886&rsqb; &lbrack;USACO07NOV&rsqb;牛继电器Cow Relays(矩阵)

    传送门 矩阵快速幂,本质是floyd 把 * 改成 + 即可 注意初始化 因为只有100条边,所以可以离散化 #include <cstdio> #include <cstring& ...

  9. &lbrack;洛谷P2886&rsqb; 牛继电器Cow Relays

    问题描述 For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race ...

随机推荐

  1. 教你一招:解决windows xp系统开机出现&OpenCurlyDoubleQuote;disk checking has been canceled”

    问题重现: 问题分析: 系统的注册表被修改了. 问题解决: 1.(临时解决)开机时,按ESC或ENTER键取消. 2.(彻底解决)修改注册表文件. Win + R 打开运行 Regedit ,进入注册 ...

  2. 使用Monkey进行压力测试

    Android可以使用Monkey向应用发送一连串的随机操作,就好像把手机交给一只猴子让它任意操作一样,以此来检测应用是否健壮,是否容易出错或崩溃.操作的类型包括触屏.移动.按键等. Monkey的语 ...

  3. Linux -- 文件统计常用命令

    标签(空格分隔): Linux sort -- 文件内排序命令 sort将文件的每一行作为一个单位,相互比较,比较原则是从首字符向后,依次比较其ASCII码. 按每行升序排序: sort seq.tx ...

  4. Eclipse中出现-访问限制由于对必需的库XX具有一定限制,因此无法访问类型

    在项目上点击右键,找到构建路径.然后选择配置配置路径.按如下步骤来配置: 1 点击库选项 2把系统库扩展开来 3点击访问规则 4点击右边的添加按钮 5添加访问规则 6 分辨率设为可访问 7规则模式设为 ...

  5. 【linux 命令】:查看系统开机,关机时间【转载】

    转载原文:http://www.cnblogs.com/kerrycode/p/3759395.html 看Linux开机关机时间的方法(非常全面) 1: who 命令查看 who -b 查看最后一次 ...

  6. 安卓从业者应该关注:Android 6&period;0的运行时权限

    Android 6.0,代号棉花糖,自发布伊始,其主要的特征运行时权限就很受关注.因为这一特征不仅改善了用户对于应用的使用体验,还使得应用开发者在实践开发中需要做出改变. 没有深入了解运行时权限的开发 ...

  7. eclipse &plus;cvs 的基本使用方法(一)

    很多时候我们在做项目开发时,会用到cvs,现在我给大家介绍一下关于eclipse下怎么使用cvs管理功能,eclipse本身是自带cvs的,我们只要简单设置一下让它连接到cvs服务器上.    看下图 ...

  8. 记录一个NPE问题

    昨天在做公司项目时,我在一处地方加了一个逻辑校验,之后测了下发现在方法调用深处有一处NPE,来源于另一个同事的代码. 其实NPE本应该是个Java编程中老掉牙的问题,但我觉得这一处错误还是比较典型的, ...

  9. VS2017编译GDAL&lpar;64bit&rpar;&plus;解决C&num;读取Shp数据中文路径的问题

    编译GDAL过程比较繁琐,查阅了网上相关资料,同时通过实践,完成GDAL的编译,同时解决了SHP数据中文路径及中文字段乱码的问题,本文以“gdal-2.3.2”版本为例阐述整个编译过程. 一.编译准备 ...

  10. vue-cli脚手架中webpack配置基础文件详解

    一.前言 原文:https://segmentfault.com/a/1190000014804826 vue-cli是构建vue单页应用的脚手架,输入一串指定的命令行从而自动生成vue.js+wep ...