hdu4751 最短路+背包dp
Problem Description Bob gets tired of playing games, leaves Alice, and travels to Changsha alone. Yuelu Mountain, Orange Island, Window of the World, the Provincial Museum etc...are scenic spots Bob wants to visit. However, his time is very limited, he can’t visit them all.
Assuming that there are N scenic spots in Changsha, Bob defines a satisfaction value Si to each spot. If he visits this spot, his total satisfaction value will plus Si. Bob hopes that within the limited time T, he can start at spot S, visit some spots selectively, and finally stop at spot E, so that the total satisfaction value can be as large as possible. It's obvious that visiting the spot will also cost some time, suppose that it takes C
i units of time to visit spot i ( 0 <= i < N ).
Always remember, Bob can choose to pass by a spot without visiting it (including S and E), maybe he just want to walk shorter distance for saving time.
Bob also has a special need which is that he will only visit the spot whose satisfaction value is
strictly larger than that of which he visited last time. For example, if he has visited a spot whose satisfaction value is 50, he would only visit spot whose satisfaction value is 51 or more then. The paths between the spots are bi-directional, of course.
Input The first line is an integer W, which is the number of testing cases, and the W sets of data are following.
The first line of each test data contains five integers: N M T S E. N represents the number of spots, 1 < N < 100; M represents the number of paths, 0 < M < 1000; T represents the time limitation, 0 < T <= 300; S means the spot Bob starts from. E indicates the end spot. (0 <= S, E < N)
The second line of the test data contains N integers C
i ( 0 <= C
i <= T ), which means the cost of time if Bob visits the spot i.
The third line also has N integers, which means the satisfaction value Si that can be obtained by visiting the spot i ( 0 <= S
i < 100 ).
The next M lines, each line contains three integers u v L, means there is a bi-directional path between spot u and v and it takes L units of time to walk from u to v or from v to u. (0 <= u, v < N, 0 <= L <= T)
Output Output case number in the first line (formatted as the sample output).
The second line contains an integer, which is the greatest satisfaction value.
If Bob can’t reach spot E in T units of time, you should output just a “0” (without quotation marks).
Sample Input
1
4 4 22 0 3
1 1 1 1
5 7 9 12
0 1 10
1 3 10
0 2 10
2 3 10
Sample Output
Case #1:
21
/** hdu4751 最短路+背包dp 題目大意：給定一個圖網絡，想要從起點走到終點，可以訪問一些點，訪問需要耗費一定的時間，每訪問一個點都可以得到該點的一個滿意值，當然也可以選擇路過該點，路過不 需要時間，那麼問題來了：在給定時間內能否從起點走到終點，如果能可以得到的最大花費值是多少？ 解題思路：這個題目的意思有很多細節需要揣摩：1，路過點不用花費時間，但也不能得到滿意值，2，最後到達終點即可，不一定非要訪問終點 先求出每兩個點之間的最短路，然後dp轉移。dp的時候注意一點，訪問的下一點要比當前點的滿意度要高，這就要求我們在算滿意度點為i的點的時候，所有滿意度 小於i的點的狀態都要已知，所以處理的時候要滿意度遞增先排個序。。最後值得一提的是一定要注意重邊，坑死我了 */ #include #include #include #include using namespace std; const int INF=0x3f3f3f3f; const int maxn=105; int n,m,s,t,e; int a[maxn][maxn],dp[maxn][350],Hash[maxn]; struct note { int w,v,id; bool operator <(const note &other) const { return vt)break; maxx=max(maxx, dp[i][j]); } } printf(Case #%d: %d ,++tt,maxx); } return 0; } /** 1 4 4 22 0 3 22 22 22 22 5 7 9 12 0 1 10 1 3 10 0 2 10 2 3 10 */
