RC-u3 战利品分配

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

int n , m , k , p , st , ed;
int w[N];
int dist[N]; //dist -> 0 -> not check
int dq[N]; //记录当前点的p玩家具备的战利品价值

vector<int> e[N];

int zuiduanlu , ans;

int calc() {
    queue<int> q;
    q.push(st);
    dist[st] = 1;

    while(q.size()) {
        auto t = q.front();q.pop();

        for(auto u : e[t]) {
            if(dist[u] == 0) {
                dist[u] = dist[t] + 1;
                q.push(u);
            }
        }
    }
    return dist[ed];
}

void bfs() {
    memset(dist , 0 , sizeof dist);
    queue<int> q;
    q.push(st);
    dist[st] = 1;
    if(p == 1)dq[st] = w[st];

    while(q.size()) {
        auto t = q.front();
        q.pop();

        if(dist[t] > zuiduanlu)break;
        //当前节点是否已经到达终点！
        if(t == ed) {
            ans = max(ans , dq[t]);
            continue;
        }

        for(auto u : e[t]) { 

            if(dist[u] != 0 && u != ed)continue;

            dist[u] = dist[t] + 1;
            dq[u] = dq[t];
            if((dist[u] % k == p % k)) {
                dq[u] += w[u];
            }
            if(u == ed && dist[t] + 1 == zuiduanlu)ans = max(ans , dq[u]);
            q.push(u);

        }
    }
}

signed main() {
    cin >> n >> m >> k >> p;
    for(int i = 1; i <= n; i ++) {
        cin >> w[i];
    }

    for(int i = 1; i <= m; i ++) {
        int u , v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    cin >> st >> ed;

    zuiduanlu = calc();

    bfs();

    cout << ans << endl;
}