hdu 1385 floyd字典序
Minimum Transport Cost
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11017 Accepted Submission(s):
3058
of cities there may be one transportation track or none. Now there is some cargo
that should be delivered from one city to another. The transportation fee
consists of two parts:
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.
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:
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.
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
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<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ql(a,b) memset(a,b,sizeof(a))
int e[105][105],b[105];
int path[105][105];
void floyd(int n)
{
int i,j,k;
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
if(e[i][j]>b[k]+e[i][k]+e[k][j]){
e[i][j]=b[k]+e[i][k]+e[k][j];
path[i][j]=path[i][k];
}
else if(e[i][j]==b[k]+e[i][k]+e[k][j]&&path[i][j]>path[i][k]){
path[i][j]=path[i][k];
}
}
}
void print(int u,int v)
{
int k;
if(u==v)
{
printf("%d",v);
return ;
}
k=path[u][v];
printf("%d-->",u);
print(k,v);
}
int main()
{
int n,m,i,j,k,a,c,t=1;
while(cin>>n&&n){
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
scanf("%d",&e[i][j]);
if(e[i][j]==-1) e[i][j]=inf;
path[i][j]=j;
}
for(i=1;i<=n;++i) cin>>b[i];
floyd(n);
while(cin>>a>>c&&(a+1||c+1)){
printf("From %d to %d :\nPath: ",a,c);
print(a,c);
printf("\nTotal cost : %d\n\n",e[a][c]);
}
}
return 0;
}
最新文章
- WORD中字数和字符
- codeforces 499A.Inna and Pink Pony 解题报告
- <;<;Effective Java>;>;之善用组合而不是继承
- 使用memcache(thinkphp框架学习)
- C#的一个异常
- jade初学
- Android之——Fragment生命周期(日志截图版)
- java中try 与catch的使用
- AndroidStudio运行项目出现Unsupported method: AndroidProject.getPluginGeneration()错误解决办法
- 马拉车算法——求回文子串个数zoj4110
- 【省选十连测之九】【DP】【组合计数去重】【欧拉函数】基本题
- 死磕 java集合之TreeMap源码分析(一)- 内含红黑树分析全过程
- c# 判断一个string[]是否全包含另一个string[]
- Coroutine的原理以及实现
- 利用 John the Ripper 破解用户登录密码
- Intellij-idea 如何编译maven工程
- |和||、&;&;和&;
- PHPExcel使用-使用PHPExcel导入文件
- C语言专题-基本数据类和占位符
- 编译安装keepalived,实现双主mysql高可用