HIIT Speedrun

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

vector<int> g[111];

int d[111][(1<<3)][2];

int inf=1e9;

int addc(int b, char c, int x, int mid){
    if (x==mid) return b;
    if (c=='H'){
        b|=1;
    } else if(c=='I'){
        b|=2;
    } else if(c=='T'){
        b|=4;
    }
    return b;
}

int n;
string s;

int test(int mid){    
    for (int i=1;i<=n;i++){
        for (int b=0;b<(1<<3);b++){
            for (int y=0;y<2;y++){
                d[i][b][y]=inf;
            }
        }
    }
    d[1][addc(0, s[0], 1, mid)][1==mid]=0;
    queue<tuple<int, int, int>> bfs;
    bfs.push(make_tuple(1, addc(0, s[0], 1, mid), 1==mid));
    while (!bfs.empty()){
        int x,b,y;
        tie(x,b,y) = bfs.front();
        bfs.pop();
        int td=d[x][b][y];
        for (int nx:g[x]){
            //if (y && nx==mid) continue;
            int nb=addc(b, s[nx-1], nx, mid);
            int ny=(y || nx==mid);
            if (d[nx][nb][ny]>td+1){
                d[nx][nb][ny]=td+1;
                bfs.push(make_tuple(nx, nb, ny));
            }
        }
    }
    return d[n][7][1];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int m;
    cin>>n>>m;
    cin>>s;
    for (int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int ans=inf;
    for (int i=1;i<=n;i++){
        if (s[i-1]=='I'){
            ans=min(ans, test(i));
        }
    }

    if (ans<inf){
        cout<<ans<<endl;
    }else{
        cout<<"IMPOSSIBLE"<<endl;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED