去北京看奥运
Time Limit:1000MS Memory Limit:65536K
Total Submit:398 Accepted:116
Description
2008年将到，王飞同学化了九牛二虎之力搞到了2张2008年奥运会足球赛决赛的门票。真是开心啊！他爸爸准备开车跟他一起去北京看球赛。不过门票费好贵啊，所以他爸爸说了，这个钱要在下学期的生活费里扣（好抠门），不过如果他能让从杭州去北京的油费最省（油价最近涨的好厉害啊），那么就不扣生活费了。
哈哈，这个就难不倒他了。在ACM里可不是白混的。
很快他算出了汽车从杭州到北京必须要加几次油，并查出了到北京要经过哪几个城市，每个城市有哪些加油站以及从某城市各加油站到另一城市各加油站的距离和路况算出了各加油站之间的耗油量。
下面是不是很easy?
Input
有多个测试案例。第一行先输入测试案例的数目T。
对于每个测试案例，第一行输入一个整数n表示将在中途n（0 < n < 40)个城市中加油，后面紧跟着是n个整数代表每个城市有几个加油站(每个城市加油站不超过10个）。
以下n+1行，每行由3个Si,Ej,L一组组成的好几对整数，该行以0结束。表示从前一城市Si第i个加油站（杭州的话就是家拉）出发到该城市第j个加油站消耗的油量为L升。
Output
对于每个测试，输出一行，内容为最小总耗油量。
Sample Input
1
2 2 3
1 1 3 1 2 1 0
1 1 2 1 2 7 2 1 8 2 2 9 2 3 4 0
1 1 5 2 1 6 3 1 6 0
Sample Output
10
中文题，这种是最简单的动态规划问题了，从左往右折，每次求得各个加油站上最小耗油量！！！
看代码的时候发现自己写的看不懂了。。。。悲剧！！！代码实现能力仍然是个话题啊！！
代码如下：
#include<stdio.h>
#include<string.h>
int main()
{
int num1[50];
int num2[50]; //暂时存储中间结果
int num3[50]; //结果数组
int t,n,k,s,e,i,g,m,j;
int l;
scanf("%d",&t); //组数
for(m=0;m<t;m++)
{
for(j=0;j<15;j++) //初始化num3
num3[j]=0;
scanf("%d",&n); //城市个数
for(i=0;i<n;i++) //城市加油站个数没用。。。
scanf("%d",&k);
for(i=0;i<n+1;i++) //n个城市要走n步
{
for(j=0;j<15;j++) //初始化
num2[j]=1000000;
for(j=0;j<15;j++) //初始化
num1[j]=0;
while(scanf("%d",&g)!=EOF&&g!=0)//参数判定
{
s=g;
scanf("%d %d",&e,&l);
if(num2[e]==1000000)
{
num1[e]=num3[s]+l;
num2[e]=num1[e];
}
else if(num3[s]+l<=num2[e])
{
num1[e]=num3[s]+l;
num2[e]=num1[e];
}
}
for(j=0;j<50;j++) //结果存储
num3[j]=num2[j];
}
printf("%d\n",num3[1]); //输出结果
}
return 0;
}
posted on 2010-09-14 09:59
jince 阅读(294)
评论(0) 编辑 收藏 引用 所属分类:
Questions