floyd算法

喜欢ヅ旅行 2021-06-22 15:37 339阅读 0赞

floyd算法是通过动态规划特别是记住公式，f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。
    因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层。
    那为什么判断不连通的条件为大于0x3f3f3f3f/2呢？，因为可能存在不连通的点但是能把那个点更新了，比如i到j的距离是0x3f3f3f3f但是j到k的距离是-1，可以更新最短距离就不是0x3f3f3f3f了

#include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int maxn=1e5+10;
    int n,m,k;

int g[210][210];
    void floyd(){ 
    	int k,i,j;
    	for(int k=1;k<=n;k++){ 
    		for(int i=1;i<=n;i++){ 
    			for(int j=1;j<=n;j++){ 
    				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    			}
    		}
    	}
    }

int main(){ 
    	cin>>n>>m>>k;
    	for(int i=1;i<=n;i++){ 
    		for(int j=1;j<=n;j++){ 
    			 if(i==j){ 
    			 	g[i][j]=0;
    			 }
    			 else{ 
    			 	g[i][j]=0x3f3f3f3f;
    			 }
    		}
    	}
    	while(m--){ 
    		int a,b,c;
    		cin>>a>>b>>c;
    		g[a][b]=min(g[a][b],c);
    	}
    	floyd();
    	while(k--){ 
    		int a,b;
    		cin>>a>>b;
    		if(g[a][b]>0x3f3f3f3f/2){ 
    			cout<<"impossible"<<endl;
    		}
    		else{ 
    			cout<<g[a][b]<<endl;
    		}
    	}
    	
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，339人围观）

还没有评论，来说两句吧...

相关阅读

相关 Floyd算法实战

<table> <tbody> <tr> <td> <h2>畅通工程续</h2> <strong>Time Limit: 3000/1000 MS (Java

太过爱你忘了你带给我的痛/ 2024年02月18日 22:54/ 0 赞/ 6 阅读

相关 Floyd-Warshal算法

![0_1315389826sAEs.gif][] 先来简单分析下,由于矩阵中对角线上的元素始终为0,因此以k为中间点时,从上一个矩阵到下一个矩阵变化时,矩阵的第k行,第k

港控/mmm°/ 2024年02月18日 22:54/ 0 赞/ 7 阅读

相关 Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦

雨点打透心脏的1/2处/ 2023年07月17日 15:59/ 0 赞/ 75 阅读

相关 Floyd算法实现(.)

最短路径算法 Floyd算法实现 const int INF = 65535; void GetShortestPath_Floyd(MGraph

缺乏、安全感/ 2022年12月27日 08:41/ 0 赞/ 84 阅读

相关 Floyd判圈算法

关于该算法，wiki上有详细说明。 https://en.wikipedia.org/wiki/Cycle\_detection\Tortoise\_and\_hare h

港控/mmm°/ 2022年12月13日 11:18/ 0 赞/ 82 阅读

相关 1128 信使（floyd算法）

1. 问题描述：战争时期，前线有 n 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在

约定不等于承诺〃/ 2022年09月15日 15:52/ 0 赞/ 164 阅读

相关 PHP实现Floyd算法

Floyd算法相比于迪杰特斯拉算法又是在于方便理解，逻辑清晰但不方便记录路径 public function run() { @set

柔情只为你懂/ 2022年06月15日 04:28/ 0 赞/ 125 阅读

相关 Floyd-Warshall算法

　　Floyd也是采用动态规划的方案来解决在一个有向图G=（V，E）上每对顶点间的最短路径问题。运行时间为Θ（V3）。算法分析：　　用邻接矩阵map\[\]\[\]存储

以你之姓@/ 2021年12月17日 03:03/ 0 赞/ 254 阅读

相关图论 Floyd算法

Floyd算法　　　　时间复杂度O (n^3) 　　空间复杂度O (n^2) 用处　　可以求任意两个点之间的最短路径长度。　　得出的邻接矩阵存储 i 到 j 的

青旅半醒/ 2021年12月15日 05:01/ 0 赞/ 199 阅读

相关 floyd算法

floyd算法是通过动态规划特别是记住公式，f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = m

喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 340 阅读