Baekjoon 1916번 최소비용 구하기

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n, m;
vector<int> dist(1001, INF);
vector<pair<int, int>> adj[1001]; // cost, vertex

vector<int> dijkstra(int src){
    dist[src] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, src));
    while(!pq.empty()){
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if(dist[here] < cost) continue;
        for(int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i].first;
            int nextDist = cost + adj[here][i].second;
            if(dist[there] > nextDist){
                dist[there] = nextDist;
                pq.push(make_pair(-nextDist, there));
            }
        }
    }
    return dist;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    int s, e, c; // start, end, cost    
    for(int i = 0; i < m; i++){
        cin >> s >> e >> c;
        adj[s].push_back(make_pair(e, c));
    }
    int src, dest;
    cin >> src >> dest;
    auto ans = dijkstra(src);
    cout << ans[dest];
    return 0;
}

다익스트라의 최단 경로 알고리즘을 이용하여 풀이할 수 있다.

이때 최단거리를 저장하는 dist 배열을 함수 속에 선언하고 사용하면 메모리 초과가 일어난다. 찾아본 결과 서버(리눅스)의 프로세스 당 스택 사이즈는 1~8mb 뿐이기 때문에 스택을 초과할 수 있다고 한다. 힙 메모리 공간을 사용하는 전역변수로 선언하면 해결된다.

참고

전역변수와 지역변수의 메모리 사용 차이에 대한 질문...