算法1

回溯算法

看到过了8个测试点还以为自己能拿80分，结果看了其他佬的题解发现可能才10-20分……TT
但是至少没交白卷（）

C++ 代码

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=110,M=5010;

int n,m,l,k;
int c[N],u[M],v[M],d[M];
int h[N],ne[M];
vector<int> ans;
int maxLen,cnt;

void init(){
    cin >> n >> m >> l >> k;
    for(int i=0;i<n;i++){
        scanf("%d",&c[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%d",&u[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%d",&v[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%d",&d[i]);
    }
}

void transfer(){
    for(int i=0;i<m;i++){
        int start=u[i];
        ne[i]=h[start];
        h[start]=i;
    }
}

void backtracing(int start){
    if(cnt>l)return;
    if(start==n-1 && cnt<=l){
        ans.push_back(maxLen);
        return;
    }
    for(int i=h[start];i!=-1;i=ne[i]){
        int end=v[i];
        if(c[start]==c[end])continue;
        maxLen+=d[i];
        cnt++;
        backtracing(end);
        maxLen-=d[i];
        cnt--;

    }
}


int main(){
    init();
    memset(h,-1,sizeof h);
    transfer();
    cnt++;
    backtracing(0);
    sort(ans.begin(),ans.end());
    printf("%d",ans[ans.size()-1]);
}