去北京看奧運
Time Limit:1000MS Memory Limit:65536K
Total Submit:398 Accepted:116
Description
2008年將到，王飛同學(xué)化了九牛二虎之力搞到了2張2008年奧運會足球賽決賽的門票。真是開心啊！他爸爸準(zhǔn)備開車跟他一起去北京看球賽。不過門票費好貴啊，所以他爸爸說了，這個錢要在下學(xué)期的生活費里扣（好摳門），不過如果他能讓從杭州去北京的油費最省（油價最近漲的好厲害啊），那么就不扣生活費了。
哈哈，這個就難不倒他了。在ACM里可不是白混的。
很快他算出了汽車從杭州到北京必須要加幾次油，并查出了到北京要經(jīng)過哪幾個城市，每個城市有哪些加油站以及從某城市各加油站到另一城市各加油站的距離和路況算出了各加油站之間的耗油量。
下面是不是很easy?
Input
有多個測試案例。第一行先輸入測試案例的數(shù)目T。
對于每個測試案例，第一行輸入一個整數(shù)n表示將在中途n（0 < n < 40)個城市中加油，后面緊跟著是n個整數(shù)代表每個城市有幾個加油站(每個城市加油站不超過10個）。
以下n+1行，每行由3個Si,Ej,L一組組成的好幾對整數(shù)，該行以0結(jié)束。表示從前一城市Si第i個加油站（杭州的話就是家拉）出發(fā)到該城市第j個加油站消耗的油量為L升。
Output
對于每個測試，輸出一行，內(nèi)容為最小總耗油量。
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
中文題，這種是最簡單的動態(tài)規(guī)劃問題了，從左往右折，每次求得各個加油站上最小耗油量！！！
看代碼的時候發(fā)現(xiàn)自己寫的看不懂了。。。。悲劇！！！代碼實現(xiàn)能力仍然是個話題啊！！
代碼如下：
#include<stdio.h>
#include<string.h>
int main()
{
int num1[50];
int num2[50]; //暫時存儲中間結(jié)果
int num3[50]; //結(jié)果數(shù)組
int t,n,k,s,e,i,g,m,j;
int l;
scanf("%d",&t); //組數(shù)
for(m=0;m<t;m++)
{
for(j=0;j<15;j++) //初始化num3
num3[j]=0;
scanf("%d",&n); //城市個數(shù)
for(i=0;i<n;i++) //城市加油站個數(shù)沒用。。。
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)//參數(shù)判定
{
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++) //結(jié)果存儲
num3[j]=num2[j];
}
printf("%d\n",num3[1]); //輸出結(jié)果
}
return 0;
}
posted on 2010-09-14 09:59
jince 閱讀(320)
評論(0) 編輯 收藏 引用 所屬分類:
Questions