[SWEA] 1249 보급로

 

문제는 길고 거창해보이지만 요약하면 각 칸마다 가중치가 있고 S부터 G까지 최소비용의 거리를 구하라는 얘기다

다익스트라 기본문제다!

 

크게 설명할 필요가 없는 문제같다..!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
 
int map[111][111];
int d[111][111];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int n;
 
bool inner(int x, int y){
    return (0<=x && x<n && 0<=y && y<n);
}
 
int dijk(){
    memset(d,-1,sizeof(d));
    priority_queue<pair<int,pair<int,int>>> pq;
    pq.push({0,{0,0}});
 
    while(!pq.empty()){
        int cost = -pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
 
        if(d[x][y] == -1) d[x][y]=cost;
 
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(!inner(nx,ny)) continue;
            int ncost = -cost-map[nx][ny];
            if(d[nx][ny]==-1) pq.push({ncost,{nx,ny}});
        }
    }
    return d[n-1][n-1];
}
 
 
int main(){
    //freopen("input.txt","r",stdin);
    int tc; scanf(" %d",&tc); int c=1;
    while(tc--){
        scanf(" %d",&n);
 
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf(" %1d",&map[i][j]);
            }
        }        
        printf("#%d %d\n",c++,dijk());
    }