BOJ 1916번 최소비용 구하기

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

github : https://github.com/junho0956/Algorithm/blob/master/1916/1916/%EC%86%8C%EC%8A%A4.cpp

 

임의의 출발점에서 원하는 정류장까지의 각 최단거리를 구하려면

다익스트라의 개념을 활용해야합니다.

우선순위 큐를 이용하여 nlogn 에 구현하였습니다

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
typedef pair<int, int> pii;
#define INF 987654321
 
bool visit[1001];
int dist[1001];
int N, M;
priority_queue<pii, vector<pii>, greater<pii> > q;
vector<pii> v[1001];
 
void dijkstra(int start, int finish) {
    dist[start] = 0;
    q.push({ 0,start });
    while (!q.empty()) {
        int cur = q.top().second;
        int len = q.top().first;
        q.pop();
 
        if (visit[cur]) continue;
        visit[cur] = true;
 
        for (int i = 0; i < v[cur].size(); i++) {
            int vertex = v[cur][i].first;
            int distance = v[cur][i].second;
            if (!visit[vertex] && len + distance < dist[vertex]) {
                dist[vertex] = len + distance;
                q.push({ len + distance, vertex });
            }
        }
    }
}
 
void solve() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) dist[i] = INF;
    for (int i = 0; i < M; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({ e,w });
    }
    int s, e; cin >> s >> e;
    dijkstra(s, e);
    cout << dist[e];
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}