BOJ 1261: 알고스팟 작성일 2020-02-23 https://www.acmicpc.net/problem/1261 2월동안 187문제 풀기(지난달 누적 87개) (60/187) 다익스트라 연습 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <bits/stdc++.h> using namespace std; int N, M; int arr[100][100]; int cost[100][100]; struct P { int x, y, v; }; auto cmp = [](P a, P b) { return a.v > b.v; }; priority_queue<P,vector<P>,decltype(cmp)> pq(cmp); const int dx[4] = {-1,0,1,0}; const int dy[4] = {0,1,0,-1}; inline bool bound(int x, int y) { return x >= 0 && y >= 0 && x < N && y < M; } const int INF = 1e9; int main() { scanf("%d %d", &M, &N); for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) { scanf("%1d", &arr[i][j]); cost[i][j] = INF; } pq.push({0,0,0}); cost[0][0] = 0; while(pq.size()) { P cur = pq.top(); pq.pop(); if(cur.v != cost[cur.x][cur.y]) continue; for(int i = 0; i < 4; i++) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if(!bound(nx,ny)) continue; if(cost[nx][ny] <= cur.v + arr[nx][ny]) continue; cost[nx][ny] = cur.v + arr[nx][ny]; pq.push({nx,ny,cost[nx][ny]}); } } cout << cost[N-1][M-1]; }