boj/20968.cpp at main · joonghak/boj · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define ll long long
using namespace std;

const ll INF = 1e17 + 7;
const ll DIV = 987654321;

int n, k;

int arr[50505];
int nxt[55][50505], prv[55][50505];
string ad[55];

vector<int> adj[50505];

ll dist[50505];

int main()
{
    fastio;
    cin >> n >> k;
    for(int i = 1;i<= n;i++){
        cin >> arr[i];
    }
    for(int i = 1;i<=k;i++) cin >> ad[i], ad[i] = '0' + ad[i];

    for(int i = 1;i<=k;i++){
        int p = 0;
        for(int j = 1;j<=n;j++){
            prv[i][j] = p;
            if(arr[j] == i) p = j;
        }
        p = n + 1;
        for(int j = n;j>= 1;j--){
            nxt[i][j] = p;
            if(arr[j] == i) p = j;
        }
    }

    for(int i = 1;i<=n;i++){
        int c = arr[i];
        for(int j = 1;j<=k;j++){
            if(ad[c][j] == '0') continue;

            if(prv[j][i] >= 1) adj[i].push_back(prv[j][i]);
            if(nxt[j][i] <=n) adj[i].push_back(nxt[j][i]);
        }
        if(ad[c][arr[n]] =='1'){
            if(nxt[arr[n]][i] <= n) adj[i].push_back(n);
        }
    }
    fill(dist, dist + n + 2, INF);
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<>> pq;
    pq.push({0, 1});
    dist[1] = 0;
    while(!pq.empty()){
        auto[d, cur] = pq.top();
        pq.pop();
        if(dist[cur] != d) continue;
        for(int i : adj[cur]){
            ll nd = d + abs(i - cur);
            if(dist[i] > nd){
                dist[i] = nd;
                pq.push({nd, i});
            }
        }
    }

    if(dist[n] == INF) cout << -1;
    else cout << dist[n];

    return 0;
}