博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷P1613 跑路
阅读量:6759 次
发布时间:2019-06-26

本文共 978 字,大约阅读时间需要 3 分钟。

这么简单的题都想了半天,肯定是智商低

看起来对Floyd的掌握还不够熟练呢

总之,把2^k的状态扔在最外围循环就ok了

// luogu-judger-enable-o2#include 
#include
#include
#include
using namespace std;const int MAXN = 50 + 2;int N, M;bool d[MAXN][MAXN][63];int f[MAXN][MAXN];int main(){ cin>>N>>M;memset(f, 0x3f, sizeof(f)); for(int i = 1, u, v; i <= M; i++){ scanf("%d%d", &u, &v); d[u][v][0] = 1, f[u][v] = 1; } for(int p = 1; p < 63; p++) for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) if(d[i][k][p - 1] && d[k][j][p - 1]) d[i][j][p] = 1, f[i][j] = 1; for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); cout<
<

 

转载于:https://www.cnblogs.com/wsmrxc/p/9291737.html

你可能感兴趣的文章
MSI文件的制作
查看>>
计算机基础------网络
查看>>
A线段树
查看>>
SpringMVC视图解析器 转
查看>>
转s2sh三大框架整合过程(仅供参考)
查看>>
构建之法---阅读报告
查看>>
{ubuntu}乱七八糟重命名为1 2 3.....png
查看>>
【树形DP】【P1364】医院放置
查看>>
JSP第5次测试---测试分析
查看>>
区别:并发与并行
查看>>
SQL 2000 无法添加、更新或删除从MSX服务器上发起的作业
查看>>
python18-day5
查看>>
企业称重防作弊概述 称重软件
查看>>
ASP.NET 大文件下载的实现思路及代码
查看>>
得到一个范围的随机数函数
查看>>
8148 8168 中移植live55 出现except rtsp 中途莫名的断流
查看>>
Linux——搭建PHP开发环境第三步:mysql
查看>>
Vue.nextTick和Vue.$nextTick
查看>>
经典算法-链表(golang)
查看>>
leetcode — search-a-2d-matrix
查看>>