P1796 湯姆斯的天堂夢_NOI導刊2010提高（05）

題目描述

湯姆斯生活在一個等級為0的星球上。那裡的環境極其惡劣，每天12小時的工作和成堆的垃圾讓人忍無可忍。他嚮往著等級為N的星球上天堂般的生活。

有一些航班將人從低等級的星球送上高一級的星球，有時需要向駕駛員支付一定金額的費用，有時卻又可以得到一定的金錢。

湯姆斯預先知道了從0等級星球去N等級星球所有的航線和需要支付（或者可以得到）的金錢，他想尋找一條價格最低（甚至獲得金錢最多）的航線。

輸入輸出格式

輸入格式：

第一行一個正整數N(N≤100)，接下來的數據可分為N個段落每段的第一行一個整數Ki(Ki≤100)，表示等級為i的星球有Ki個。

接下來的Ki中第Tij行依次表示與等級為i，編號為i的星球相連的等級為i-l的星球的編號和此航線需要的費用（正數表示支出，負數表示收益，費用的絕對值不超過1000）。

每行以0結束，每行的航線數≤100。

輸出格式：

輸出所需（或所得）費用。正數表示支出，負數表示收益。

輸入輸出樣例

3
2
1 15 0
1 5 0
3
1 -5 2 10 0
1 3 0
2 40 0
2
1 1 2 5 3 -5 0
2 -19 3 -20 0

-1

說明

對於100%的數據N≤100 Ki≤100。

樣例解釋：

用t數組表示上一層的狀態，用d數組表示本層的狀態

轉移方程d[i]=min(d[i],t[k]+m)

然後再把t數組替換為d數組

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9')
11     {c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9')
13     {x=x*10+(c-48);c=getchar();}
14     flag==1?n=-x:n=x;
15 }
16 int n,m;
17 int a[10001];
18 int dp[10001][31];
19 int l,d[110],t[110]; 
20 int main()
21 {
22     int i,j,k;
23     read(n);
24     for (i=1;i<=n;i++)
25     {
26         read(k);
27         for (j=1;j<=k;j++)
28         {
29             d[j]=0x7ffff;        //將d[j]初始化 
30             read(l);
31             while (l!=0)
32             {
33                 read(m);
34                 if (d[j]>t[l]+m) d[j]=t[l]+m;
35                 read(l);
36             }
37         }
38         for (j=1;j<=k;j++)
39             t[j]=d[j];
40     }
41     int ans=1000000;
42     for (i=1;i<=k;i++){
43         if (ans>d[i]) ans=d[i];
44     }
45     printf("%d",ans);
46     return 0;
47 }