POJ 3613 Cow Relays floyd + 快速幂

2023-11-08 09:08
文章标签 快速 cow poj floyd 3613 relays

本文主要是介绍POJ 3613 Cow Relays floyd + 快速幂,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本题的大意就是问从S 到 T 经过边得个数恰为k的最短路是多少。


参考国家队集训论文 08年的  矩阵乘法在信息学中的应用

01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数

 对应于这道题,对邻接图进行K次floyd之后,C[i][j]就是点i到j正好经过K条边的最短路

但是K次floyd难免复杂度太高了。 所以可以使用快速幂的方法,二分的往上求解

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#define MAXN 1005
#define MAXM 500005
#define INF 1000000000
using namespace std;
int k, m, s, t;
int ans[MAXN][MAXN], mp[MAXN][MAXN], tmp[MAXN][MAXN], dis[MAXN][MAXN];
int used[MAXN], v[MAXN], num;
void floyd(int c[][MAXN], int a[][MAXN], int b[][MAXN])
{for(int k = 0; k < num; k++)for(int i = 0; i < num; i++)for(int j = 0; j < num; j++)if(c[v[i]][v[j]] > a[v[i]][v[k]] + b[v[k]][v[j]])c[v[i]][v[j]] = a[v[i]][v[k]] + b[v[k]][v[j]];
}
void copy(int a[][MAXN], int b[][MAXN])
{for(int i = 0; i < num; i++)for(int j = 0; j < num; j++){a[v[i]][v[j]] = b[v[i]][v[j]];b[v[i]][v[j]] = INF;}
}
void slove(int k)
{while(k){if(k & 1){floyd(dis, ans, mp);copy(ans, dis);}floyd(tmp, mp, mp);copy(mp, tmp);k >>= 1;}
}
int main()
{int x, y, w;scanf("%d%d%d%d", &k, &m, &s, &t);for(int i = 0; i <= 1000; i++){for(int j = 0; j <= 1000; j++){mp[i][j] = INF;tmp[i][j] = INF;dis[i][j] = INF;ans[i][j] = INF;}ans[i][i] = 0;}num = 0;for(int i = 0; i < m; i++){scanf("%d%d%d", &w, &x, &y);if(!used[x]){used[x] = 1;v[num++] = x;}if(!used[y]){used[y] = 1;v[num++] = y;}if(mp[x][y] > w)mp[x][y] = mp[y][x] = w;}slove(k);printf("%d\n", ans[s][t]);return 0;
}


这篇关于POJ 3613 Cow Relays floyd + 快速幂的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/368940

相关文章

Linux如何快速检查服务器的硬件配置和性能指标

《Linux如何快速检查服务器的硬件配置和性能指标》在运维和开发工作中,我们经常需要快速检查Linux服务器的硬件配置和性能指标,本文将以CentOS为例,介绍如何通过命令行快速获取这些关键信息,... 目录引言一、查询CPU核心数编程(几C?)1. 使用 nproc(最简单)2. 使用 lscpu(详细信

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

8种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

《8种快速易用的PythonMatplotlib数据可视化方法汇总(附源码)》你是否曾经面对一堆复杂的数据,却不知道如何让它们变得直观易懂?别慌,Python的Matplotlib库是你数据可视化的... 目录引言1. 折线图(Line Plot)——趋势分析2. 柱状图(Bar Chart)——对比分析3

一文教你Java如何快速构建项目骨架

《一文教你Java如何快速构建项目骨架》在Java项目开发过程中,构建项目骨架是一项繁琐但又基础重要的工作,Java领域有许多代码生成工具可以帮助我们快速完成这一任务,下面就跟随小编一起来了解下... 目录一、代码生成工具概述常用 Java 代码生成工具简介代码生成工具的优势二、使用 MyBATis Gen

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展,动画效果已经成为了网页设计中不可或缺的一部分,本文将深入探讨animation.css的工作原理,如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs

SpringBoot快速搭建TCP服务端和客户端全过程

《SpringBoot快速搭建TCP服务端和客户端全过程》:本文主要介绍SpringBoot快速搭建TCP服务端和客户端全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录TCPServerTCPClient总结由于工作需要,研究了SpringBoot搭建TCP通信的过程

一文教你Python如何快速精准抓取网页数据

《一文教你Python如何快速精准抓取网页数据》这篇文章主要为大家详细介绍了如何利用Python实现快速精准抓取网页数据,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录1. 准备工作2. 基础爬虫实现3. 高级功能扩展3.1 抓取文章详情3.2 保存数据到文件4. 完整示例

快速修复一个Panic的Linux内核的技巧

《快速修复一个Panic的Linux内核的技巧》Linux系统中运行了不当的mkinitcpio操作导致内核文件不能正常工作,重启的时候,内核启动中止于Panic状态,该怎么解决这个问题呢?下面我们就... 感谢China编程(www.chinasem.cn)网友 鸢一雨音 的投稿写这篇文章是有原因的。为了配置完

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.