应该用dp做的但是我太懒懒得看题解了 留到考试的时候看
超时20分代码：
#include<bits/stdc++.h>
using namespace std;
int N, M, L, K;
struct Edge {int to, length;Edge(int to, int length) :to(to), length(length) {}
};
vector<int> color;//颜色标签
vector<vector<Edge>> graph;//邻接表
//vector<int> path;
int max_length = 0;//最大长度
//i:当前遍历节点
//colors：目前找到的颜色集合
//num:结点个数
void dfs(int i,set<int> colors,int num,int now_length) {if (num > L) {return;}else {//说明找到了if (i == N - 1) {/*for (int i = 0; i < path.size(); i++)cout << path[i] << " ";cout << endl;*/max_length = max(max_length, now_length);return;}//没找到继续遍历else {for (Edge e : graph[i]) {int to = e.to;int length = e.length;int col = color[to];//说明当前颜色不存在if (colors.find(col) == colors.end()) {//path.push_back(to);colors.insert(col);dfs(to, colors, num + 1, now_length + length);colors.erase(col);//path.pop_back();}}}}}
//找到最长观光路线:
//颜色各不相同 结点数小于等于L
//越长越好
void solve() {set<int> c;c.insert(color[0]);dfs(0, c, 1, 0);cout << max_length;
}
int main() {//N:结点个数(0~N-1)//M:边的个数//L:理想观光路线节点上限//K:颜色种类(0~K-1)cin >> N >> M >> L >> K;cin.ignore();color.resize(N);for (int i = 0; i < N; i++) {cin>>color[i];}//重置图的大小graph.resize(N);vector<int> U(M), V(M), D(M);for (int i = 0; i < M; i++) {cin>>U[i];}for (int i = 0; i < M; i++) {cin >> V[i];}for (int i = 0; i < M; i++) {cin >> D[i];}//构建图for (int i = 0; i < M; i++) {Edge e = Edge(V[i], D[i]);graph[U[i]].push_back(e);}solve();return 0;
}
