2015
09-16

# Travel in time

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 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.

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)

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)

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

Case #1:
21

Floyd + Spfa + dp。先用Floyd预处理出所有点对之间的最短路，然后考虑到始点和终点是必须经过的，并且可以不游玩，于是就不能用原来的始点和终点，我们考虑新加入原点和终点，并且原点花费时间和满意值都为0（这样保证不会对结果做出影响），终点花费时间为0，满意值大于满意值的最大值（保证如果可以到达原来终点一定可以到达新终点）。接下来就是从新建图了，新原点到旧原点的路程为0，新原点到别的点的路程为旧原点到该点的距离。终点建边同理。然后别的边正常处理即可。

对于dp[ i ][ j ]表示当前点为 i ， 使用时间 j 获得的最大满意度。则就变成很明显的Spfa了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))

using namespace std;

const int N = 110;
const int M = N * N;
const int INF = 0x3f3f3f3f;

struct Edge
{
int u, v, c;
}E[M];

struct Node
{
int u, tim;
};

int fir[N], next[M], tot;
int G[N][N], n, m, t, s, e, cas = 1;
int C[N], S[N], dp[N][N * 3];

void Add_Edge(int u, int v, int c)
{
E[tot].u = u, E[tot].v = v, E[tot].c = c;
next[tot] = fir[u], fir[u] = tot ++;
}

void input()
{
int u, v, c, i, j;
scanf("%d%d%d%d%d", &n, &m, &t, &s, &e);
CLR(G, INF);
for(i = 0; i < n; i ++)
scanf("%d", &C[i]);
for(i = 0; i < n; i ++)
{
scanf("%d", &S[i]);
G[i][i] = 0;
}
for(i = 0; i < m; i ++)
{
scanf("%d%d%d", &u, &v, &c);
G[u][v] = G[v][u] = min(c, G[u][v]);
}
}

void floyd()
{
int i, j, k;
for(k = 0; k < n; k ++)
for(i = 0; i < n; i ++)
for(j = 0 ; j < n; j ++)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}

void init()
{
int i, j;tot = 0;CLR(fir, -1);
S[n] = C[n] = 0;
S[n + 1] = N;C[n + 1] = 0;
for(i = 0; i < n; i ++)
{
if(i != s) Add_Edge(n, i, G[s][i]);
if(i != e) Add_Edge(i, n + 1, G[e][i]);
else Add_Edge(e, n + 1, 0);
}
for(i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
if(S[j] > S[i])
s = n; e = n + 1;n += 2;
}

void Spfa()
{
int v, i, j, c, ans;
queue<Node> Q;CLR(dp, 0);
dp[s][0] = 0;Node A, B;
A.u = s;A.tim = 0;Q.push(A);
while(!Q.empty())
{
A = Q.front();Q.pop();
for(i = fir[A.u]; ~i; i = next[i])
{
v = E[i].v;c = E[i].c;
int tmp = A.tim + c + C[v];
if(tmp <= t && dp[v][tmp] < dp[A.u][A.tim] + S[v])
{
dp[v][tmp] = dp[A.u][A.tim] + S[v];
B.u = v;
B.tim = tmp;
Q.push(B);
}
}
}
ans = 0;
for(i = 0; i <= t; i ++)
{
ans = max(ans, dp[e][i]);
}
printf("Case #%d:\n%d\n", cas ++, max(ans - N, 0));
}

int main()
{
//freopen("input.txt", "r", stdin);
int w;
scanf("%d", &w);
while(w --)
{
input();
floyd();
init();
Spfa();
}
}