백준 4485:녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485

아니요.. 링크라구요 링크!!!...

이번문제도.. 다익스트라 문제예요.. 하지만 입력에서는 배열이네요? 그러면 상하좌우로 연결된 그래프라고 생각하면 편합니다아.. 큐에는 좌표가 들어갑니다.

(0, 0)에서 (N-1, N-1)까지 최소로 갈 수있는 합을 구하면됩니다.. 그리구 시작비용이 0이아니라! (0, 0)에 있는 값이 되겠네요.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
#define r first
#define c second
const char dr[4] = { 0,1,0,-1 };
const char dc[4] = { -1,0,1,0 };
 
typedef pair<int, int> pos;//좌표
typedef pair<int, pos> PAIR;//좌표까지의 최소비용
 
int main(void) {
    ios::sync_with_stdio(false);
 
    vector<int> ans;
    while (true) {
        int N; cin >> N;
        if (N == 0) break;
 
        priority_queue<PAIR, vector<PAIR>, greater<PAIR>> pq;
        vector<vector<bool>> visited(N, vector<bool>(N, false));
        vector<vector<int>> graph(N, vector<int>(N));
        vector<vector<int>> cost(N, vector<int>(N, 1e9));
        for (auto& row : graph) {
            for (auto& col : row) {
                cin >> col;
            }
        }
 
        pq.push(PAIR(graph[0][0], pos(0, 0)));
        cost[0][0] = graph[0][0];//시작값 주의
 
        while (!pq.empty()) {//다익스트라 알고리즘
            pos cur;
            do {
                cur = pq.top().second; pq.pop();
            } while (!pq.empty() && visited[cur.r][cur.c]);
 
            if (visited[cur.r][cur.c]) break;
            visited[cur.r][cur.c] = true;
 
            for (int i = 0; i < 4; i++) {//넣을때 4방향 그래프 탐색해요
                pos next(cur.r + dr[i], cur.c + dc[i]);
                if (!(next.r < 0 || next.c < 0 || next.r >= N || next.c >= N)) {
                    //범위 안에 든다면
                    if (cost[next.r][next.c] > cost[cur.r][cur.c] + graph[next.r][next.c]) {
                        cost[next.r][next.c] = cost[cur.r][cur.c] + graph[next.r][next.c];
                        pq.push(PAIR(cost[next.r][next.c], next));//다음 좌표까지의 최소비용 갱신
                    }
                }
            }
        }
        ans.push_back(cost[N - 1][N - 1]);//답 저장
    }
 
    int s = ans.size();
    for (int i = 0; i < s; i++) {
        cout << "Problem " << i + 1 << ": " << ans[i] << endl;
    }
 
    return 0;
}