HIIT Speedrun

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n, m;
const long long inf=1e18l;
long long sh[111][(101)<<4];

vector<int> rt[101010];
priority_queue<pair<pair<long long, int>, int> > pq;

char ch[111];

int main(){
  cin >> n >> m;
  cin >> ch;
  for (int i=0;i<m;++i){
    int a, b;
    cin >> a >> b;
    rt[a].push_back(b);
    rt[b].push_back(a);
  }
  for (int i=0;i<111;++i) for (int j=0;j<((101)<<4);++j) sh[i][j]=inf;
  sh[1][0]=0;
  pq.push({{0,0},1});
  
  bool ok=0;
  long long ans=0;
  while (!pq.empty()){
    pair<pair<long long, int>, int> cp=pq.top();
    pq.pop();
    long long d=-cp.F.F;
    int c=cp.S;
    int t=cp.F.S;
    if (sh[c][t]<d) continue;
    
    if (ch[c-1]=='H'){
      t|=1;
    }else if (ch[c-1]=='I'){
      if (~t&2){
        t|=2|(c<<4);
      }else if (t>>4 != c){
        t|=4;
      }
    }else if (ch[c-1]=='T'){
      t|=8;
    }
//     cout << c << ", " << d << ", " << t << endl;
    if (c==n && (t&15)==15){
      ok=1;
      ans=d;
      break;
    }
    for (auto w:rt[c]){
      if (sh[w][t]<=d+1) continue;
      sh[w][t]=d+1;
      pq.push({{-d-1, t}, w});
    }
  }
  if (ok) cout << ans << "\n";
  else cout << "IMPOSSIBLE\n";
}

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