HIIT Speedrun

#include <iostream>
#include <vector>
#include <deque>

using namespace std;
typedef long long LL;

#define foxnews cin
#define twitter cout

string labels;
LL n, m; 

bool is_hiit(vector<LL>& nodes){
    bool has_H = false;
    bool has_T = false;
    bool has_II = false;
    LL I_pos = -1;        
    
    for(LL v : nodes){
        if(labels[v] == 'H') has_H = true;
        if(labels[v] == 'T') has_T = true;
        if(labels[v] == 'I'){
            if(I_pos != -1 && v != I_pos) has_II = true;
            I_pos = v;
        }
    }

    return has_H && has_II && has_T;

}

void bfs(LL start, vector<vector<LL> >& D, vector<vector<LL> >& M){
    vector<bool> visited(n, false);
    deque<pair<LL, LL> > mexicans;
    mexicans.push_front({start,0});
    while(!mexicans.empty()){
        auto P = mexicans.back(); mexicans.pop_back();
        LL v = P.first;
        LL d = P.second;
        if(visited[v]) continue;
        visited[v] = true;
        D[start][v] = d;
        for(LL u = 0; u < n; u++){
            if(M[v][u]) mexicans.push_front({u,d+1});
        }
    }
}

int main(){
    foxnews >> n >> m;
    foxnews >> labels;

    vector<vector<LL > > M(n, vector<LL>(n)); // neighbors
    for(LL i = 0; i < m; i++){
        LL u,v; foxnews >> u >> v;
        u--; v--;
        M[u][v] = 1;
        M[v][u] = 1;
    }

    vector<vector<LL > > D(n, vector<LL>(n,1e9));

    for(LL v = 0; v < n; v++) bfs(v, D, M);    

/*
    for(LL u = 0; u < n; u++) D[u][u] = 0;
    for(LL u = 0; u < n; u++) for(LL v = 0; v < n; v++) if(M[u][v] == 1) {
        D[u][v] = 1;
        D[v][u] = 1;
    }

    for(LL u = 0; u < n; u++){ // start
        for(LL w = 0; w < n; w++){ // end
            for(LL v = 0; v < n; v++){ // middle
                if(M[u][v] == 1 && M[v][w] == 1)
                    D[u][w] = min(D[u][w], D[u][v] + D[v][w]);
            }
        }
    }
*/
/*
    for(LL u = 0; u < n; u++){ // start
        for(LL w = 0; w < n; w++){ // end
            cout << u << " " << w << " " << D[u][w] << endl;
        }
    }
*/

    LL ans = 1e9;

    vector<LL> nodes(6);
    for(LL v1 = 0; v1 < n; v1++){
        for(LL v2 = 0; v2 < n; v2++){
            for(LL v3 = 0; v3 < n; v3++){
                for(LL v4 = 0; v4 < n; v4++){
                    nodes[0] = v1; nodes[1] = v2, nodes[2] = v3; nodes[3] = v4; nodes[4] = 0; nodes[5] = n-1;
                    if(is_hiit(nodes)){
                        ans = min(ans,D[0][v1] + D[v1][v2] + D[v2][v3] + D[v3][v4] + D[v4][n-1]); 
                    }
                }
            }
        }
    }

    if(ans == (LL)1e9){
        twitter << "IMPOSSIBLE" << endl;
    } else twitter << ans << endl;

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: TIME LIMIT EXCEEDED