NSOJ Minimum Transport Cost
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.
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:
Output
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
看来自己floyd还是没有深刻的理解....用Floyd存路径很是不错...get....
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 111 int cost[MAX];
int mp[MAX][MAX],path[MAX][MAX];
int n; void floyd()
{
for(int k=; k<=n; k++)
for(int i=; i<=n; i++)
for(int j=; j<=n; j++){
int ans=mp[i][k]+mp[k][j]+cost[k];
if(mp[i][j]>ans){
mp[i][j]=ans;
path[i][j]=path[i][k];
}
else if(mp[i][j]==ans && path[i][j]>path[i][k]){
path[i][j]=path[i][k];
}
}
} int main()
{
while(~scanf("%d",&n)&&n!=){
for(int i=; i<=n; i++){
for(int j=; j<=n; j++){
if(i!=j)
mp[i][j]=INF;
else
mp[i][j]=;
path[i][j]=j;
}
}
for(int i=; i<=n; i++){
for(int j=; j<=n; j++){
scanf("%d",&mp[i][j]);
if(mp[i][j]==-)
mp[i][j]=INF;
}
}
for(int i=; i<=n; i++){
scanf("%d",&cost[i]);
}
floyd();
int a,b;
while(~scanf("%d%d",&a,&b)){
if(a==-&&b==-)
break;
printf("From %d to %d :\n",a,b);
printf("Path: ");
int s=a;
while(s!=b){
printf("%d-->",s);
s=path[s][b];
}
printf("%d\n",b);
printf("Total cost : %d\n\n", mp[a][b]);
} }
}
最新文章
- MySQL安装常见问题(找不到文件,系统服务无法启动...)
- c++中继承和java中继承的对比
- Qt中在图片上叠加显示文字
- 冒泡,快排算法之javascript初体验
- arcgis engine 开发教程系列
- Gen_server行为分析与实践
- socket基本操作
- [数据库连接字符串] Access 连接字符串
- vpn分配多ip的配置
- codeforces Upgrading Array
- leetCode 24. Swap Nodes in Pairs (双数交换节点) 解题思路和方法
- 我的第一个jQuery插件--表格隔行变色
- pipeline结合GridSearchCV的一点小介绍
- Linux学习笔记 --服务器优化
- 修改Tomcat访问的端口号
- 在C++98基础上学习C++11新特性
- Android 访问地址
- Redis-08.命令参数详解
- fiddler接口测试,js代码修改日志展示(埋点用)
- [java]转:String Date Calendar之间的转换