백준(BOJ) 1916 최소비용구하기 C++ 풀이

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

1916번: 최소비용 구하기

문제 풀이에 이용된 알고리즘: 다익스트라

 

굉장히 간단한 최단 경로 문제였다.

 

버스 노선은 곧 간선을 의미한다. 이 때 버스가 양방향 통행이 가능하다는 말이 없으므로, 양방향 간선이 아니라 방향성이 있는 것으로 생각해야 한다.

 

최단 경로를 구하기 위해서, 다익스트라나 플로이드 알고리즘을 생각할 수 있는데 플로이드 알고리즘은 N^3의 시간복잡도를 갖는다.

 

도시의 개수가 최대 1000개이므로 플로이드를 적용할 경우, 시간 제한이 0.5초인 해당 문제는 풀 수 없다고 판단하여(실제로 확인해보지는 않았다....) 다익스트라 알고리즘을 이용하였다.

 

다익스트라의 구현을 위해서 cmp 구조체나, 우선순위 큐를 사용하는 방법 등의, 구현을 위한 문법을 아래 코드에서 확인하면 유용할 것이다.

 

visited 배열을 사용한 이유는, 이미 최단 경로 비용이 계산된 정점인지 확인하기 위함이다. 꼭 visited 배열이 아니더라도 단순한 dist[cur]와 distance 값의 비교를 통해 continue하는 방법도 있지만, 때때로 스스로도 헷갈리는 경우가 발생하여.. 직관적인 visited 배열을 사용하는 편이다.

 

/* BOJ 1916 최소 비용 구하기 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
const int INF = 1e9;
int n, m, dist[1001];
bool visited[1001];
vector<pair<int, int>> edges[1001];
 
struct cmp
{
    bool operator()(pair<int, int> p1, pair<int, int> p2)
    {
        return p1.second > p2.second;
    }
};
 
void dijkstra(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    pq.push({ start, 0 });
    dist[start] = 0;
 
    while (!pq.empty())
    {
        int cur = pq.top().first, distance = pq.top().second;
        pq.pop();
 
        if (visited[cur])
            continue;
 
        visited[cur] = true;
 
        for (auto edge : edges[cur])
        {
            int next = edge.first;
            int cost = edge.second;
 
            if (dist[next] > distance + cost)
            {
                dist[next] = distance + cost;
                pq.push({ next, dist[next] });
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
 
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].push_back({ b, c });
    }
 
    int s, d;
    cin >> s >> d;
    
    dijkstra(s);
 
    cout << dist[d] << endl;
 
    return 0;
}