[백준 1916번] 최소비용 구하기

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

1916번: 최소비용 구하기

풀이)

자원 측면에서 vector를 사용하였고, 특정 노드에 방문했을 때 갈 수 있는 노드들을 거리가 최소가 된다면 갱신하는 방식으로 구현하였다. 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int N, M, start, finish;
int dist[1001];
vector <pair<int,int> > graph[1001];
queue<int> q;

int dijkstra(int start) {
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < graph[x].size(); i++) {
            int nx = graph[x][i].first;
            int cost = graph[x][i].second;
            if (dist[nx] == -1 || dist[x] + cost < dist[nx]) {
                dist[nx] = dist[x] + cost;
                if(nx != finish)
                    q.push(nx);
            }
        }
    }
    return dist[finish];
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(dist, -1, sizeof(dist));
    cin >> N >> M;
 
    while (M--){
        int b, c, d;
        cin >> b >> c >> d;
        graph[b].push_back(make_pair(c, d));
    }
    cin >> start >> finish;
    cout << dijkstra(start) << "\n";
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!