Luogu P3125

bzoj 4102

思路

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;
}