# 2242. Maximum Score of a Node Sequence

[LA:4000, Paris:10000, London:10000, Rome:1000]
LA <--> Paris
LA <--> London
London <--> Paris
London <--> Rome

seen = set()
LA seen({LA}) -> P seen({LA, P}) -> L -> R seen({LA, P, L, R}) 100
backtrack(L)
-> R -> L 80

def happyTrip(cities, flights): 
    # cities [["LA", 100], ["Paris", 80]]
    # flights [["LA", "Paris"], ["Paris", "Rome"]]
    
    
    # step 1 build relations
    happyOfCity = {}
    for city, happyNum in cities:
        happyOfCity[city] = happyNum
    
    canflyTo = defaultdict(list)
    for city1, city2 in flights:
        canflyTo[city1].append(city2)
        canflyTo[city2].append(city1)
        
    # happyOfCity
    #[LA:4000, Paris:10000, London:10000, Rome:1000]
    
    # canflyTo ["LA":["Paris", "London"]]
    
    ans = 0
    # step 2 backtrack function
    def backtrack(curCity, seen, happyCount, numOfCity):
        # LA, {LA}, 4000, 1
        # Paris, {LA, Paris}, 14000, 2
        if numOfCity == 4:
            ans = max(ans, happyCount)
            return
  
        # O(N*N*N)
        for nextCity in canflyTo[curCity]:
            if nextCity in seen:
                continue
            seen.add(nextCity)
            backtrack(nextCity, seen, happyCount + happyOfCity[nextCity], numOfCity+1)
            seen.remove(nextCity)

    # step 3 loop all city
    # O(N) * O(N*N*N) = O(N**4)
    for city in happyOfCity:
        # "LA"
        backtrack(city, set({city}), happyOfCity[city], 1)
        
    return ans

# A -> B* -> C -> D
# F -> B* -> C -> D
        
    

class Solution {
public:
    int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
        int n = scores.size();
        vector<vector<pair<int,int>>> G(n); // score, v

        // 1. record neighbors (score, v) for every vertex u
        for (auto &e : edges) {
            G[e[0]].push_back( {scores[e[1]], e[1]} );
            G[e[1]].push_back( {scores[e[0]], e[0]} );
        }

        // 2. sort neighbors according to score (large to small) for every vertex u
        for(auto &edgeV : G) {
            sort(edgeV.rbegin(), edgeV.rend());
        }

        // 3. to form a path x1->x2->x3->x4, enumerate all posiible x2->x3, and O(1) to find x1 and x4.
        int ans = -1;
        for (auto &e : edges){
            int x2 = e[0];
            int x3 = e[1];
            for(int i=0;i<min(3, (int)G[x2].size());i++){
                for(int j=0;j<min(3, (int)G[x3].size());j++){
                    int x1 = G[x2][i].second;
                    int x4 = G[x3][j].second;
                    if( x1!=x3 && x2!=x4 && x1!=x4 ){
                        ans = max(ans, scores[x1]+scores[x2]+scores[x3]+scores[x4]);
                    }
                }
            }
        }
        return ans;
    }
};