http://acm.hdu.edu.cn/showproblem.php?pid=1385
题意: 找一个路径使得从一个地方坐的士到另一个地方花费最小,其中除了起点和终点,途中经过的站点要收费
Sample Input
5
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4
-1 -1
0
Sample Output
From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21
From 3 to 5 :
Path: 3-->4-->5
Total cost : 16
From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define inf 999999999 //用0x3fffffff太大溢出,纠结了良久
#define M 205
int dist[M][M], n, b[M], path[M][M];
void floyd ()
{
int i, j, k;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
path[i][j] = j; //记录路径数组初始化,表示从i到j经过的第一个站
for (k = 1; k <= n; k++)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
int tp = dist[i][k] + dist[k][j] + b[k];
//溢出之地,因为+了b[k],其实先判断是否有路会更保险
if (tp < dist[i][j])
dist[i][j] = tp, path[i][j] = path[i][k];
else if (tp == dist[i][j] && path[i][k] < path[i][j])
path[i][j] = path[i][k]; //按字典序记录路径
}
}
}
}
int main()
{
int i, j, u, v, tp;
while (scanf ("%d", &n), n)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf ("%d", dist[i]+j);
if (dist[i][j] == -1)
dist[i][j] = inf;
}
}
for (i = 1; i <= n; i++)
scanf ("%d", b+i);
floyd();
while (scanf ("%d%d", &u, &v), (u != -1 || v != -1))
{
printf ("From %d to %d :\n", u, v);
printf ("Path: %d", u);
tp = u;
while (u != v)
{
printf ("-->%d", path[u][v]);
u = path[u][v];
}
printf ("\nTotal cost : %d\n\n", dist[tp][v]);
}
}
return 0;
}
分享到:
相关推荐
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。采用C++实现
Floyd最短路径算法利用三层循环实现弗洛伊德最短路径算法。
实现了Floyd最短路径算法,两个实例,代码中写有说明,简单易懂,非常适合初学者学习路径分析算法。
Floyd算法是经典的最短路径算法之一,应用广泛,可以求解多对多和一对一的最短路;
Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似,对于有向的NP问题提供求解的方法。
floyd计算最短路径,只需要更改邻接矩阵
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
用MFC来完成Floyd算法的最短路径基本功能求法(有界面)。
最短路径算法 floyd
最短路径floyd算法实现最短路径floyd算法实现最短路径floyd算法实现最短路径floyd算法实现
教科书上的Floyd算法只能输出path,无法给出具体的路径描述,本代码可以输出具体的路径选择
floyd最短路径算法源码,因为资源分为0导致我挣不到分没法下资源,所以我是被逼的.........
根据Floyd最短路径算法的三层循环,设计了动态优化新算法。动态优化新算法设计了独特的动态Ay集合、可 发表B和可达表A,分别对原算法的外层循环、中层循环和内层循环进行极小化的运算。在极小化的处理过程中。为保证...
Floyd最短路径算法.pdf
Matlab语言实现Floyd最短路径算法并计算路径链,路径链保存在列表中。可用于图的两点间最短路径的计算。
Floyd最短路径算法在配送中心选址中的应用.pdf
MATLAB中计算已知有向图、邻接矩阵情况下的最短路径
Floyd算法求任意两点间的最短路,数据结构c语言! 文件操作