Minimum Transport Cost
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3923Accepted Submission(s): 989
Problem Description
These are N cities in Spring country. Between each pair 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.
Input
First 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:
Output
From 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-->3Total cost : 21From 3 to 5 :Path: 3-->4-->5Total cost : 16From 2 to 4 :Path: 2-->1-->5-->4Total cost : 17
Source
#include<stdio.h>
#include<string.h>
#define size 1000
int val[size],map[size][size],used[size],min[size],n,start[size],end[size],flag,pre[size];
char s1[1300],s2[1300];
int ok(int n1,int n2,int s)//比较字典序大小
{
int i,k;
i=0;
s1[i++]=n1+'0';
k=pre[n1];
while(k!=s)
{
s1[i++]=k+'0';
k=pre[k];
}
s1[i++]=s+'0';
s1[i]='\0';
strrev(s1);//把字符串翻转过来
i=0;
s2[i++]=n1+'0';
k=n2;//因为依然是n1(j)为最后一个 通过n2(pos)架桥
while(k!=s)
{
s2[i++]=k+'0';
k=pre[k];
}
s2[i++]=s+'0';
s2[i]='\0';
strrev(s2);
if(strcmp(s2,s1)<0)
return 1;
else return 0;
}
void find_short(int s)
{
int i,j,mm,pos;
memset(used,0,sizeof(used));
for(i=1;i<=n;i++)
{
min[i]=map[s][i];
if(map[s][i]!=999999999) //这一步居然忘记了 阿弥陀佛 记住这个千万不能少
pre[i]=s;
}
min[s]=0;used[s]=1;
for(i=2;i<=n;i++)
{
mm=999999999;
for(j=1;j<=n;j++)
{
if(!used[j]&&mm>min[j])
{
pos=j;
mm=min[j];
}
}
if(mm==999999999) break;
used[pos]=1;
for(j=1;j<=n;j++)
if(!used[j]&&min[pos]+map[pos][j]+val[pos]<min[j])
{
min[j]=min[pos]+map[pos][j]+val[pos];
pre[j]=pos;
}
else
if(!used[j]&&min[pos]+map[pos][j]+val[pos]==min[j])
if(ok(j,pos,s)) pre[j]=pos;//如果pos之前的字典序较小那么更新
}
}
void print(int s,int e)
{
int a[size],i,k;
k=0;
a[k++]=e;
i=e;
while(s!=i)
{
i=pre[i];
a[k++]=i;
}
printf("Path: ");
for(i=k-1;i>0;i--)
printf("%d-->",a[i]);
printf("%d\n",a[0]);
}
int main()
{
int i,j,s,e,num;
while(scanf("%d",&n)&&n!=0)
{
num=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]==-1) map[i][j]=999999999;
}
for(i=1;i<=n;i++)
scanf("%d",&val[i]);
while(1)
{
scanf("%d %d",&s,&e);
if(s==-1&&e==-1) break;
start[num]=s;
end[num++]=e;
}
for(i=0;i<num;i++)
{
flag=0;
find_short(start[i]);
printf("From %d to %d :\n",start[i],end[i]);
if(start[i]!=end[i])
print(start[i],end[i]);
else printf("Path: %d\n",start[i]);
printf("Total cost : %d\n",min[end[i]]);
printf("\n");
}
}
return 0;
}
/*记录路径思路就是加入一个pre[]数组 时时更新每个点前面的点是什么 另外不要忘记从始点出发到i的所有的pre都要赋值初始点
本题要求按字典序找出最短的路径 一开始我感到很恐惧 不知道怎么做 其实心里没有必要那么害怕 只要尝试着一点一点的去做
不要不敢尝试就退却 把大问题分解成一个一个小问题 硬着头皮也要上 (看了别人代码才A了)*/
分享到:
相关推荐
最短路径 贪心实现代码 hdu 最短路 dijkstra 算法
适合于单源最短路径算法,采用的是dijkstra最短路径算法。简单易懂,本题在hdu.edu.cn上通过了,网址是http://acm.hdu.edu.cn/search.php?field=problem&key=2680。由于不能同时上传两个文件,所以我放到另一个去了...
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
HDU的一题........HDU DP动态规
hdu1001解题报告
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu 1005.比较简单的一道题,有兴趣的可以看看。
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu动态规划算法集锦