好题，长沙邀请赛的一道题。
这种题还是蛮常见的，SPFA+DP优化，记得上次北大校赛就有一道。
根据题意，我们可以虚拟两个超级源点和超级汇点，源点到所有点的距离都是这段距离加上参观的时间。所有点到汇点的距离就是该点到终点的距离。
这样控制之后，对于终点就有2个选择了，路过或者参观。
对于途中除起点终点以外的点，我们可以先进行一遍floyd，然后根据他们的val值进行连边，值是两点之间的距离加上参观的时间。这样对于每一点其实也有两个选择了，可以参观该点，即a -> b，也可以路过该点,即a -> b(路过，floyd保证了这一点) ->c。
然后从源点开始跑一遍spfa,最后在终点和超级汇点之间找到一个最大值，就是答案。
这道题期间犯了一个很2的错误，我已经不能多说了。
下面是代码：
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
using namespace std;
#define N 105
#define M 20005
#define K 305
int tim[N] , val[N] ;
int Map[N][N] ;
int n , m , s , e , t ;
struct kdq {
int s , e, l ,next ;
} ed[M] ;
int head[N] , num ;
void add(int s , int e ,int l) {
ed[num].e = e ;
ed[num].l = l ;
ed[num].next = head[s] ;
head[s] = num ++ ;
}
int vis[N][K] ;
int dp[N][K] ;// dp[i][j]表示点i在时间j的时候的最大值
PII qe[N * 1000] ;
void init() {
mem(head ,-1 ) ;
num = 0 ;
mem(val ,0) ;
mem(tim ,0) ;
for (int i = 0 ; i < N ; i ++ ) {
for (int j = 0 ; j < N ; j ++ )
Map[i][j] = inf ;
Map[i][i] = 0 ;
}
cin >> n >> m >> t >> s >> e ;
for (int i = 0 ; i < n ; i ++ )scanf("%d",&tim[i]) ;
for (int i = 0 ; i < n ; i ++ )scanf("%d",&val[i]) ;
while(m -- ) {
int x , y , z ;
scanf("%d%d%d",&x,&y,&z) ;
Map[x][y] = Map[y][x] = min(Map[x][y] , z) ;
}
for (int k = 0 ; k < n ; k ++ )
for (int i = 0 ; i < n ; i ++ )
for (int j = 0 ; j < n ; j ++ )
Map[i][j] = min(Map[i][j] , Map[i][k] + Map[k][j]) ;
for (int i = 0 ; i < n ; i ++ ) {
for (int j = i + 1 ; j < n ; j ++ ) {
if(Map[i][j] != inf) {
if(val[i] > val[j])//根据他的价值升序建边
add(j , i , Map[i][j] + tim[i]) ;
else if(val[j] > val[i])
add(i , j , Map[i][j] + tim[j]) ;
}
}
}
add(n , s , tim[s]) ;//S -> i , i -> E 。 S = n ,E = n + 1 。
for (int i = 0 ; i < n ; i ++ ) {
if(i != s && Map[i][s] != inf) {
add(n , i , tim[i] + Map[s][i]) ;
}
if(i != e && Map[i][e] != inf) {
add(i , n + 1 , Map[e][i]) ;
}
}
for (int i = 0 ; i < N ; i ++ ) {
for (int j = 0 ; j < K ; j ++ ) {
dp[i][j] = 0 ;
vis[i][j] = 0 ;
}
}
vis[n][0] = 1 ;
int hh = 0 , tt = 0 ;
qe[hh ++ ] = mp(n , 0) ;
while(hh > tt) {
PII tp = qe[tt ++ ] ;
int fk1 = tp.FI ;
int fk2 = tp.SE ;
vis[fk1][fk2] = 0 ;
for (int i = head[fk1] ; ~i ; i = ed[i].next ) {
int nxt = ed[i].e ;
int l = ed[i].l + fk2 ;
if(l > t)continue ;
if(dp[nxt][l] < dp[fk1][fk2] + val[nxt]) {
dp[nxt][l] = dp[fk1][fk2] + val[nxt] ;
if(!vis[nxt][l]) {
vis[nxt][l] = 0 ;
qe[hh ++ ] = mp(nxt , l) ;
}
}
}
}
int ans = 0 ;
for (int i = 0 ; i <= t ; i ++ ) {
ans = max(ans , dp[e][i]) ;
ans = max(ans , dp[n + 1][i]) ;
}
printf("%d
",ans) ;
}
int main() {
int T ;
cin >> T ;
for (int i = 1 ; i <= T ; i ++ ) {
printf("Case #%d:
",i) ;
init() ;
}
return 0 ;
}