题目大意入上图所述
具体思路实现：
首先，考虑问题的解法，因为任意时刻都不相同(没有同一个时刻刷出两个怪及以上的可能)，那么令：
那么这个题的状态转移方程其实也很好推的：
首先按照时间排序， 然后去找一下之前的时间点，能不能与这个时间点相连接，也就是说，假设前面有两个时间点
1 2 ，我考虑由1转移过来，还是由2转移过来，那么转移过来的条件就是，那个时间点的位置+那个时间点的时间到当前点的时间(k)<=当前时间点的时间(那就可以赶过来得到该权值)。
这时候 那个时间点的时间到当前点的时间 我们考虑最优状态转移，那么一定是k->i的最短路，所以我们要预处理一遍最短路。
所以m^2的算法也就显而易见，这时候去考虑如何优化状态，看一下 那个时间点的位置+那个时间点的时间到当前点的时间(k) 这个式子用符号化语言来表述的话就是：
这里其实dis[i][k]与dis[k][i]是相等的，因为图无向
考虑dis[i][k]的最大值 -> n ,因为全图只有n个点而且图联通。再基于没有时间点重复，也就说 i与i-n之前的所有的时间点 至少相差n，所以说i-n之前的可以不用去比较上述判断条件，直接转移，所以我们新开一个数组保留前缀最大，直接转移就可以了 ，复杂度 O(M*N) ~2e7
这其中有个坑，因为初始点是1，所以说起初的状态有可能从1过不来，所以dp数组的初始化不可以设置为-1，当然你可以令开一个bool数组标记当前时间点能否到达，能到达才进行转移，如果不开数组标记的话，将时间点设为-1e18(最小值)，这样的话，只要不能到达的再怎么加也不可能使得状态转移。最后遍历得最大值得时候，将ans初始化为0，就可以略去负数情况(负数即为不可到达).
/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const ll INF=1000000000000007;
const ll maxn=1e6+5;
const int mod=1e9+7;
ll n,m,p;
ll mp[205][205];
struct node{
ll p,w,t;
bool operator<(const node&x)const{
return t<x.t;
}
}save[maxn];
ll dp[maxn];//第i个时间点可以获得的最大权值
//由于时间不同，所以获得该时间点的权值必须以之前的作为前缀
//即200*n
ll cop[maxn];//保存i-200的最大转移前缀
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
if(i==k) mp[i][k]=0;
else mp[i][k]=INF;
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
mp[x][y]=mp[y][x]=1;
}
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
for(int j=1;j<=n;j++)
mp[k][j]=min(mp[k][j],mp[k][i]+mp[i][j]);
scanf("%lld",&p);
for(int i=1;i<=p;i++)
scanf("%lld%lld%lld",&save[i].t,&save[i].p,&save[i].w);
sort(save+1,save+1+p);
save[0].p=1;
save[0].t=0;
ll ans=0;
for(int i=1;i<=p;i++){
dp[i]=1e-18;
if(i>n) dp[i]=max(dp[i],cop[i-n]+save[i].w);
for(int k=1;k<=n&&i-k>=0;k++){
if(save[i-k].t+mp[save[i-k].p][save[i].p]<=save[i].t)
dp[i]=max(dp[i],dp[i-k]+save[i].w);
}
ans=max(dp[i],ans);
cop[i]=max(cop[i-1],dp[i]);
// printf("%lld ",dp[i]);
}
printf("%lld\n",ans);
return 0;
}
京公网安备 11010502036488号