BOJ)12026 BOJ 거리

문제:icpc.me/12026

B->O->J->B 로 이동가능한 경로를 n^2 으로 전부 간선을 연결해 준 뒤 다익스트라 알고리즘을 이용하여 최단거리를 구해주면 된다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n, dp[1001];
string a;
vector<vector<pair<int, int>>> vt;
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d", &n);
    vt.resize(n + 1);
    cin >> a;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((a[j] == 'B'&&a[i] == 'J') || (a[j] == 'O'&&a[i] == 'B') || (a[j] == 'J'&&a[i] == 'O'))
                vt[i].push_back({ j,(j - i)*(j - i) });
        }
    }
    priority_queue<pair<int, int>> pq;
    pq.push({ 0,0 });
    while (pq.size()) {
        int here = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
        if (dp[here] != -1)continue;
        dp[here] = cost;
        if (here == n - 1)break;
        for (auto x : vt[here]) {
            int there = x.first;
            if (dp[there] != -1)continue;
            pq.push({ -cost - x.second,there });
        }
    }
    printf("%d\n", dp[n - 1]);
    return 0;
}