# 2242. Maximum Score of a Node Sequence

{%hackmd theme-dark %}
法國 英國 非洲 中國
[100, 200, 1 , 10...] = scores
[法->英, 法->非,...] = edges

set(0 1 2 ) - 2
0 - 1 - 2 - 3
0 - 5 - 6 - 2 *

0 - 3 - 4

int traverse(int src, vector<int> &scores, unordered_map<int, vector<int>> &graph) {
    queue<pair<int, int>> q; // src, score
    q.push({src, scores[src]});
    vector<bool> visited(scores.size());

    int res = 0;
    for (int i = 0; i < 4; i++) {
        if (q.empty()) {
            res = 0;
            break;
        }
        for (int x = q.size(); x > 0; x--) {
            auto [dest, score] = q.front();
            q.pop();
            res = max(res, score);
            visited[dest] = true;
            for (auto next: graph[dest]) {
                if (!visited[next]) {
                    q.push({next, score[next] + score});
                }
            }
            visited[dest] = false;
        }
    }
    
    return res;
}
int maxScore(vector<int> &scores, vector<vector<int>> &edges) {
    // scores = [100, 200, 300];
    // edges = {{src, dest}, {src, dest}, {0, 10}}
    unordered_map<int, vector<int>> graph;
    for (auto &e: edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    
    // start from every src to get max scores
    int res = 0;
    for (int i = 0; i < scores.size(); i++) {
        res = min(res, traverse(i, scores, graph));
    }
    
    return res;
}

a0 - a - b - b0
a1 -       - b1
...        ...

###### tags: `mock interview` `面試`