思路
bfs求出点两两间的距离,按权值排序,设$f_{i}$为走到$i$为止获得最多的能量,$f_{i}=\min\limits_{val_{j}<val_{i}}\{f_{j}-dis_{j, i}+val_{i}\}$
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
struct Data{
int val, id;
bool operator <(const Data &_)const{return val<_.val;}
}a[1010];
int to[1010][15], dis[1010][1010], N, E, f[1010], pos[1010];
void bfs(int S){
std::queue<int>q;
q.push(S);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=1; i<=to[a[x].id][0]; i++)
if(!dis[a[S].id][to[a[x].id][i]] && to[a[x].id][i]!=a[S].id){
dis[a[S].id][to[a[x].id][i]]=dis[a[S].id][a[x].id]+1;
q.push(pos[to[a[x].id][i]]);
}
}
}
int main(){
scanf("%d%d", &N, &E);
for(int i=1; i<=N; i++){
a[i].id=i;
scanf("%d", &a[i].val);
scanf("%d", &to[i][0]);
for(int j=1; j<=to[i][0]; j++)
scanf("%d", &to[i][j]);
}
std::sort(a+1, a+N+1);
for(int i=1; i<=N; i++) a[i].id[pos]=i;
for(int i=1; i<=N; i++)
bfs(i);
for(int i=1; i<=N; i++) f[i]=a[i].val;
for(int i=1; i<=N; i++)
for(int j=1; j<i; j++) if(a[i].val>a[j].val && dis[a[i].id][a[j].id])
f[i]=std::max(f[i], f[j]-E*dis[a[j].id][a[i].id]+a[i].val);
int ans=0;
for(int i=1; i<=N; i++) ans=std::max(ans, f[i]);
printf("%d", ans);
return 0;
}