백준 1916번 최소비용 구하기

문제 링크입니다: https://www.acmicpc.net/problem/1916

백준 1753번(http://jaimemin.tistory.com/555)이랑 똑같은 문제였습니다.

문제에서 버스들은 결국 그래프 내의 간선들이였기 때문에 동일하게 풀 수 있는 문제였습니다.

Priority Queue는 Default로 작은 값들이 우선순위가 높기 때문에 - 를 해서 우선순위 큐에 집어넣어주는 것이 핵심이였습니다.

그리고 정점이 0이 아닌 1부터 시작하므로 n++ 해주는 것도 중요했습니다.

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

 

const int CITYMAX = 1000 + 1;

const int BUSMAX = 100000 + 1;

const int INF = 987654321;

 

int n, m;

int source, destination; //출발점, 도착점

vector<pair<int, int>> graph[CITYMAX];

 

vector<int> dijkstra(int start, int vertex)

{

        vector<int> distance(vertex, INF); //start를 기준으로 거리

        distance[start] = 0; //자기 자신한테 가는 비용 0

 

        priority_queue<pair<int, int>> pq; //Cost, Vertex

        pq.push(make_pair(0, start)); //초기 비용과 시작점

 

        while (!pq.empty())

        {

                 int cost = -pq.top().first; //거리의 부호를 바꾸어 거리가 작은 버스부터

                 int curVertex = pq.top().second;

                 pq.pop();

 

                 //최소거리를 원하므로

                 if (distance[curVertex] < cost)

                         continue;

 

                 //neighbor 다 확인

                 for (int i = 0; i < graph[curVertex].size(); i++)

                 {

                         int neighbor = graph[curVertex][i].first;

                         int neighborDistance = cost + graph[curVertex][i].second;

 

                         //최소 경로 발견시 업데이트

                         if (distance[neighbor] > neighborDistance)

                         {

                                 distance[neighbor] = neighborDistance;

                                 //거리의 부호를 바꾸어 거리가 작은 버스부터 꺼내지도록

                                 pq.push(make_pair(-neighborDistance, neighbor));

                         }

                 }

        }

        return distance;

}

 

int main(void)

{

        cin >> n >> m;

 

        n++; //정점번호 1부터 시작

 

        for (int i = 0; i < m; i++)

        {

                 int start, end, cost;

                 cin >> start >> end >> cost;

 

                 graph[start].push_back(make_pair(end, cost));

        }

       

        cin >> source >> destination;

 

        vector<int> result = dijkstra(source, n);

       

        cout << result[destination] << endl; //source->destination 거리

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~