Minimum Transport Cost Floyd 输出最短路
The cost of the transportation on the path between these cities, and
a certain tax which will be charged whenever any cargo passing through one city, except for the source and the destination cities.
You must write a program to find the route which has the minimum cost.
InputFirst is N, number of cities. N = 0 indicates the end of input.
The data of path cost, city tax, source and destination cities are given in the input, which is of the form:
a11 a12 ... a1N
a21 a22 ... a2N
...............
aN1 aN2 ... aNN
b1 b2 ... bN
c d
e f
...
g h
where aij is the transport cost from city i to city j, aij = -1 indicates there is no direct path between city i and city j. bi represents the tax of passing through city i. And the cargo is to be delivered from city c to city d, city e to city f, ..., and g = h = -1. You must output the sequence of cities passed by and the total cost which is of the form:
OutputFrom c to d :
Path: c-->c1-->......-->ck-->d
Total cost : ......
......
From e to f :
Path: e-->e1-->..........-->ek-->f
Total cost : ......
Note: if there are more minimal paths, output the lexically smallest one. Print a blank line after each test case.
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<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<deque>
#include<iomanip>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<fstream>
#include<memory>
#include<list>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 103
#define L 31
#define INF 1000000009
#define eps 0.00000001
int g[MAXN][MAXN],path[MAXN][MAXN], n, v[MAXN];//path[i][j] 表示路径i->j上 i之后的第一个结点
void Floyd()
{
for (int k = ; k <= n; k++)
{
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
if (g[i][j] > g[i][k] + g[k][j] + v[k])
{
g[i][j] = g[i][k] + g[k][j] + v[k];
path[i][j] = path[i][k];//将路径结点缩小范围确定
}
else if (g[i][j] == g[i][k] + g[k][j] + v[k])
{
if (path[i][j] > path[i][k])
{
path[i][j] = path[i][k];//比较前面的字典序
}
}
}
}
}
}
void Print(int u, int v)//递归 从i->j 可以分解为 i->path[i][j]->path[path[i][j]][j]->,,,,,j
{
if (u == v)
{
printf("%d\n", u);
return;
}
int k = path[u][v];
printf("%d-->", u);
Print(k, v);
}
int main()
{
while (scanf("%d", &n), n)
{
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
scanf("%d", &g[i][j]);
path[i][j] = j;
if (g[i][j] == -) g[i][j] = INF;
}
}
for (int i = ; i <= n; i++)
scanf("%d", &v[i]);
int f, t;
Floyd();
while (scanf("%d%d", &f, &t), f != - && t != -)
{
printf("From %d to %d :\nPath: ", f, t);
Print(f, t);
printf("Total cost : %d\n\n", g[f][t]);
}
}
}
最新文章
- mysql nonInstall 版本的安装与配置
- gnuplot: 一种更为简洁的曲线,柱状图绘图软件
- LogStash配置、使用(三)
- C# 利用ICSharpCode.SharpZipLib实现在线加密压缩和解密解压缩
- delegate和protocol
- 开启flask调试
- 【SQL Sever】SQL Sever数据库重命名
- java中使用反射往一个泛型是Integer类型的ArrayList中添加字符串,反射的案例1.
- 【Unity3D游戏开发】定制新建C#文件的头描述 (三三)
- 如何在Ubuntu 18.04中安装VMware Workstation Player
- Linux安装TeamViewer
- 转://linux下hugepages理解
- paddle实践
- word2vec 中的数学原理二 预备知识 霍夫曼树
- 在 Confluence 6 中的 Jira 设置
- Nginx Windows 安装启动
- 搞清tomcat中的编解码
- JS移动li行数据,点击上移下移(是位置的互换,不是top的偏移量改变)
- 接Window服务(二)
- [X264] MinGW编译x264,VC中调用libx264.dll-------------<;参考转>;
热门文章
- 一张图带你了解-常见面试之JUC包详解
- $CF241D\ Numbers$
- thinkphp 5 常用的助手函数
- spring controller接口中,用pojo对象接收页面传递的参数,发现spring在对pojo对象赋值时,有一定顺序的问题
- Python---查看安装路径
- 274 H-Index H指数
- [转]深入ASP.NET MVC之九:Ajax支持
- ASP.NET控件之RadioButtonList
- 浅谈.net remoting 与 webservice
- [ CodeForces 1063 B ] Labyrinth