CUBE-204: Lazanta

#include <bits/stdc++.h>

using namespace std;
using pi = pair <int, int>;
using pii = pair <pi, pi>;
using P = pair <pi, pii>;
const int N = 5e4;
const int INF = 2e9;
char ch[N+10];
vector <pi> g[N+10];
bool visited[N+10][2][2][2][2];
int dis[N+10][2][2][2][2];

int main(){

    int n, m;
    scanf("%d%d", &n, &m);

    int X = 0, M = 0, A = 0, S = 0;
    for(int i=1;i<=4;i++){
        char a;
        scanf(" %c", &a);
        if(a  == 'X') X = 1;
        else if(a == 'M') M = 1;
        else if(a == 'A') A = 1;
        else if(a == 'S') S = 1;
    }

    for(int i=2;i<=n;i++) scanf(" %c", &ch[i]);

    for(int i=1;i<=m;i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    for(int i=1;i<=n;i++){
        for(int x=0;x<2;x++){
            for(int m=0;m<2;m++){
                for(int a=0;a<2;a++){
                    for(int s=0;s<2;s++){
                        dis[i][x][m][a][s] = INF;
                    }
                }
            }
        }
    }

    if(ch[n] == 'X') X = 1;
    else if(ch[n] == 'M') M = 1;
    else if(ch[n] == 'A') A = 1;
    else if(ch[n] == 'S') S = 1;

    priority_queue <P, vector <P>, greater <P>> pq;
    pq.push({ {0, n}, { {X, M}, {A, S} } });
    dis[n][X][M][A][S] = 0;
    while(pq.size() > 0){
        int d = pq.top().first.first;
        int u = pq.top().first.second;
        int x = pq.top().second.first.first;
        int m = pq.top().second.first.second;
        int a = pq.top().second.second.first;
        int s = pq.top().second.second.second;
        pq.pop();

        if(visited[u][x][m][a][s])
            continue;
        visited[u][x][m][a][s] = true;
        dis[u][x][m][a][s] = d;
        if(u == 1 and x == 1 and m == 1 and a == 1 and s == 1){
            printf("%d", d);
            break;
        }
        for(auto vw: g[u]){
            int v = vw.first;
            int w = vw.second;
            int xx = x, mm = m, aa = a, ss = s;
            if(v != 1 and ch[v] == 'X') xx = 1;
            else if(v != 1 and ch[v] == 'M') mm = 1;
            else if(v != 1 and ch[v] == 'A') aa = 1;
            else if(v != 1 and ch[v] == 'S') ss = 1;
            if(!visited[v][xx][mm][aa][ss] and d + w < dis[v][xx][mm][aa][ss])
                pq.push({ {d+w, v}, { {xx, mm}, {aa, ss} } });
        }
    }

    return 0;
}
/**

6 7
____
XASMM
1 2 1
1 5 8
2 5 8
2 4 2
2 3 1
3 6 1
5 6 8

**/