Problem 2

#include <iostream>
#include <vector>
#include <queue>
#define ll long long
#define f first
#define s second
#define NMAX 100000
#define inf 2000000000000

using namespace std;

ll n, k, v1[100], v2[100], m[100][100], dist[NMAX+10], viz[NMAX+10];
vector <pair <ll, ll> > a, nod[NMAX+10];
priority_queue <pair <ll, ll>, vector <pair <ll, ll> >, greater <pair <ll, ll> > > pq;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(ll i=1; i<=n; i++)
        {   ll x;
            cin >> x;
            if(!v1[x]) v1[x] = i;
            v2[x] = i;
        }
    for(ll i=1; i<=k; i++)
        {   if(!v1[i]) continue;
            a.push_back({v1[i], i});
            if(v1[i] == v2[i]) continue;
            a.push_back({v2[i], i});
        }
    for(ll i=1; i<=k; i++)
        {   string s;
            cin >> s;
            for(ll j=0; j<k; j++)
                m[i][j+1] = s[j] - '0';
        }

    for(ll i=0; i<a.size(); i++)
        for(ll j=i+1; j<a.size(); j++)
            {   if(m[a[i].s][a[j].s])
                    {   if(a[i].f < a[j].f)
                            nod[a[i].f].push_back({a[j].f, 0});
                        else
                            nod[a[i].f].push_back({a[j].f, a[i].f - a[j].f});
                    }
                if(m[a[j].s][a[i].s])
                    {   if(a[j].f < a[i].f)
                            nod[a[j].f].push_back({a[i].f, 0});
                        else
                            nod[a[j].f].push_back({a[i].f, a[j].f - a[i].f});
                    }
            }
    pq.push({0, 1});
    for(ll i=2; i<=n; i++)
        dist[i] = inf;
    while(!pq.empty())
        {   pair <ll, ll> a = pq.top();
            pq.pop();
            if(a.s == n)
                {   cout << 2 * a.f + n - 1 << '\n';
                    return 0;
                }
            if(viz[a.s]) continue;
            viz[a.s] = 1;
            for(auto u : nod[a.s])
                {   if(viz[u.f]) continue;
                    ll d = a.f + u.s;
                    if(dist[u.f] > d)
                        {   dist[u.f] = d;
                            pq.push({d, u.f});
                        }
                }
        }
    cout << -1 << '\n';
    return 0;
}