在某个战争游戏中，多个玩家组成一个大型军团，攻下若干城池，并获得战利品。
具体而言，游戏中有 N 个城市，并以 M 条长度为 1 的无向道路连接，玩家们组成的军团从 S 号城市开始进攻，目的地是 T 号城市，每个城市攻下后的战利品价值为 pi。
为了合理地分配战利品，军团们定下了规矩：假设军团里有 K 位玩家，那么从 S 号城市开始，第 1 个攻下的城市分配给第 1 位玩家，第 2 个攻下的分配给第 2 位玩家，……，第 K 个攻下的分配给第 K 位玩家，第 K+1 个攻下的则重新开始计算，分配给第 1 位玩家，以此类推。
军团很强，路上所有的城市都可以轻松进攻下来。你作为军团的指挥，可以指定玩家的进攻路线。但玩家们都希望尽快结束游戏，因此 S 到 T 的距离必须是最短的。你需要做的是在最短距离的限制下选择对自己最好的线路，获得尽可能高的战利品价值。请输出你的答案。
输入格式:
输入第一行是四个数 N,M,K,P (1≤N,M≤105,1≤K≤104,1≤P≤K)，表示城市数量（于是城市从 1 到 N 编号）、连接道路数量以及你在军团中的 K 位玩家中排第 P 位（即你战利品分配在第 P 位）。
第二行是 N 个被空格隔开的非负整数，第 i 个数对应 pi (0≤pi≤104)，表示编号为 i 的城市的战利品价值（i=1,⋯,N）。
然后的 M 行，每行给出两个用空格分隔的正整数 U 和 V，表示编号为 U 和 V 的城市之间有道路连接。
最后的一行是两个正整数 S,T，表示开始的城市编号与目的地的城市编号。开始和目的地的城市也是可以进攻并获取战利品的。
输出格式:
输出一行，表示你可以取得的最大价值。
输入样例:
9 11 2 2
100 150 130 50 30 20 200 0 70
1 2
1 3
2 3
2 4
2 5
3 6
4 7
5 7
6 8
7 9
8 9
1 9
输出样例:
350题意是求图中两点的最短路径中的带权最大值，
1.先用bfs求出两点最短距离md
2.再用dfs在路径下第p个人的值：
（1）d>md时提前终止，
（2）当深度d%k==p时加入权值，
（3）当遍历至T点时终止并判断是否为最小值
#include<bits/stdc++.h>
int a[100005];
int b[100005]={0};
using namespace std;
vector<int> mp[100005];
int n,m,p;
int i,j,k;
int s,t;
int t1,t2,ok,oo;
int S=0,mS=-999999,md=999999;
int dp[100005]={0};
int cmpp(int a,int b){
return a<b;
}
void bfs(int c1,int c2){
queue<int> q;
q.push(c1);b[c1]=1;
while(!q.empty()){
int len=q.size();
for(int i=0;i<len;i++){
int ct=q.front();
q.pop();
if(ct==c2)return;
for(int it:mp[ct]){
if(b[it]==0){
b[it]=1;
q.push(it);
}
}
}
md++;
//cout<<endl<<md<<endl;
}
}
void dfs(int ss,int d){
if(d>md)return; //提前终止
if(d%k==p){S+=a[ss];} //加入权值
if(ss==t){ //终止条件
if(d<md){mS=S;md=d;if(d%k==p){S-=a[ss];}return;}
if(d==md&&mS<S)mS=S;
if(d%k==p){S-=a[ss];}
return;
}
b[ss]=1;
for(int it:mp[ss]){
if(b[it]==0){
dfs(it,d+1);
}
}
b[ss]=0; //回溯
if(d%k==p)S-=a[ss];
return;
}
int main()
{
cin>>n>>m>>k>>p;if(p==k)p=0;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(i=1;i<=m;i++){
int ct1,ct2;
scanf("%d %d",&ct1,&ct2);
mp[ct1].push_back(ct2);
mp[ct2].push_back(ct1);
}
cin>>s>>t;md=1;
memset(b,0,sizeof(b));
bfs(s,t);md++;
memset(b,0,sizeof(b));
dfs(s,1);
cout<<mS;
return 0;
}