Travel in time
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 971 Accepted Submission(s): 196
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 Ci 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 isstrictly 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 Ci ( 0 <= Ci <= 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 <= Si < 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
Source
2013 ACM-ICPC長沙賽區全國邀請賽——題目重現
Recommend
zhoujiaqi2010
題意：
n個點m條路組成的無向圖。走每一條路都會花一定的時間。參觀每一個點對應的頂點也要花一定的時間，每參觀
完一個景點會有一個滿意度。求在t時間內從起點到達終點且獲得的最大滿意度。
要求：1、每次訪問的景點的滿意度必須大於前一次訪問的景點獲得的滿意度。
2、每個景點都可以選擇訪問或者只是路過。
分析：
1、由於要求1，必須將景點按照滿意度從小到大排序。如果滿意度相等，就按編號大小排序。
2、三點式的思維，首先只考慮起點到n個點的時間和滿意度，然後通過中間插入其他可以訪問的點來更新
時間和滿意度（時間越短越好----最短路的松弛操作，相同時間下滿意度越大越好）。這樣就把所有可
能的路徑其時間相應的滿意度都找到了。最後只要從該點到達終點的時間加上到達該點的時間小於等於
t就ok了。（首先考慮的相當於到i點並訪問，而不路過其他點或者路過的點只是路過不訪問的情況）
3、注意的點很多：
(1)首先是判重。兩個點之間可能有多條路。
(2)其次就是對起點和終點的處理。起點可以訪問也可以路過。如果從起點開始用spfa
則起點是訪問了，如果從後一個節點開始spfa則起點是路過。所以要設置一個虛擬
起點。
(3)hash數組的使用。
4、狀態轉移方程：dp[i][k]表示k時間到達i點得到的滿意度。
dp[i][k]=max(dp[i][k],dp[i][k-a[i].c-maps[i][j]]+a[j].v)
感想：
才知道用algorithm頭文件中的max和min函數比自己定義的居然省時好多！！
代碼：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define INF 10000000
using namespace std;
int dp[105][305];
int maps[105][105];
int hash[105];
typedef struct
{
int c,v,id;
}Point;
Point a[105];
//按滿意度從小到大和編號從小到大排序
bool cmp(Point aa,Point bb)
{
if(aa.v!=bb.v) return aa.v<bb.v;
return aa.id<bb.id;
}
int main()
{
int T,n,m,t,s,e,i,j,k,x,y,z,ans,cnt=1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d",&n,&m,&t,&s,&e);
for(i=0;i<n;i++)
{
scanf("%d",&a[i].c);
a[i].id=i;
}
for(i=0;i<n;i++)
scanf("%d",&a[i].v);
sort(a,a+n,cmp);
for(i=0;i<n;i++)
hash[a[i].id]=i;
s=hash[s];
e=hash[e];
for(i=0;i<n;i++) //初始化任意兩點間的距離
{
for(j=0;j<n;j++)
{
//maps[i][i]=0;
if(i==j) maps[i][j]=0;
else maps[i][j]=INF;
}
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
x=hash[x];
y=hash[y];
maps[x][y]=min(z,maps[x][y]);
maps[y][x]=min(z,maps[y][x]);
}
for(k=0;k<n;k++) //松弛(spfa更新最短距離)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
maps[i][j]=min(maps[i][k]+maps[k][j],maps[i][j]);
}
}
}
printf("Case #%d:\n",cnt++);
memset(dp,-1,sizeof(dp));
for(i=0;i<n;i++) //從虛擬起點開始直接到i點並訪問所獲得的滿意度
{
for(j=a[i].c+maps[i][s];j<=t;j++) //一直枚舉到t。可能經過其他點但是沒訪問只是路過
dp[i][j]=a[i].v;
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++) //如果先經過j點再到i點用時不超過k且滿意度大則更新
{
if(a[i].v==a[j].v) break;
for(k=0;k<=t;k++) //枚舉直接到i點是時間k
{
if(maps[i][j]+a[i].c>k)
continue;
if(dp[j][k-maps[i][j]-a[i].c]==-1) continue;
dp[i][k]=max(dp[i][k],dp[j][k-maps[i][j]-a[i].c]+a[i].v);
}
}
}
ans=0;
for(i=0;i<n;i++)
{
for(j=0;j+maps[i][e]<=t;j++) //虛擬終點
{
ans=max(ans,dp[i][j]);
}
}
printf("%d\n",ans);
}
return 0;
}
//AC
//609MS
