您当前的位置: 首页 >  算法

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

Floyd 算法模板

不牌不改 发布时间:2022-03-15 22:15:08 ,浏览量:0

题目链接

基于动态规划的原理,f[k][i][j]表示通过前k个点从ij的距离,转移方程f[k][i][j] = f[k-1][i][k] + f[k-1][k][j],含义为用通过前k-1个点从i到达k的距离与通过前k-1个点从k到达j的距离 之和更新从前k个点从ij的距离。

第一维度可以忽略。

一般采用邻接矩阵来保存边,i==j的情况为 0 0 0,其余为无穷。

注意存在负边权时,当d>INF/2,说明不可达。

#include
using namespace std;
const int N = 100;

int n, e[N][N];

int main()
{
	cin >> n;
	for (int i = 1;i  e[i][j],
	e[i][j] = (e[i][j] == 0 && i != j? 0x3f3f3f3f : e[i][j]); 
	
	for (int k = 1;k             
关注
打赏
1662186765
查看更多评论
0.0837s