这种题还是蛮常见的，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\n",ans） ;
}
int main（） {
int T ;
cin 》 T ;
for （int i = 1 ; i <= T ; i ++ ） {
printf（"Case #%d:\n",i） ;
init（） ;
}
return 0 ;
} |