티스토리 뷰

알고리즘 관련/BOJ

BOJ)12026 BOJ 거리

JASON 자손9319 2017. 3. 1. 16:20

문제:icpc.me/12026


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


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
#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<intint>>> vt;
int main() {
    memset(dp, -1sizeof(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<intint>> pq;
    pq.push({ 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1629 곱셈  (0) 2017.03.05
BOJ)1201 NMK  (0) 2017.03.05
BOJ)12026 BOJ 거리  (0) 2017.03.01
BOJ)10816 숫자 카드2  (1) 2017.03.01
BOJ)1890 점프  (0) 2017.03.01
BOJ)2916 자와 각도기  (0) 2017.03.01
댓글
댓글쓰기 폼