Floyd算法（附例题） |
您所在的位置：网站首页 › floyd算法为什么可以带负权 › Floyd算法（附例题） |
|
ps：算法题调代码的两个方法：cout法和删代码法 Floyd算法 采用动态规划思想，只要用三个循环就可以了，实现简单。k必须在最外层，i和j的顺序随意。d[i][j] = min(d[i][j], d[i][k] + d[k][j]);是核心代码。Floyd算法可以用来解决多源汇最短路问题，而且可以处理带负权边的多源汇最短路问题，但无法处理带负权回路的最短路问题。AcWing 854. Floyd求最短路 给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。 再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。 数据保证图中不存在负权回路。 输入格式 第一行包含三个整数n，m，k 接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。 接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。 输出格式 共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。 数据范围 1≤n≤200, 1≤k≤n^2 1≤m≤20000, 图中涉及边长绝对值均不超过10000。 输入样例： 3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3输出样例： impossible 1AC代码： #include using namespace std; const int N = 210, INF = 1e9; int n, m, k, d[N][N]; void floyd() { for(int k = 1; k > m >> k; for(int i = 1; i x >> y >> z; d[x][y] = min(d[x][y], z); } floyd(); while(k--) { cin >> x >> y; if(d[x][y] > INF / 2) cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |