BOJ 문제풀이/최단경로 (Shortest Path)

백준 1916 : 최소비용 구하기

DevJK 2018. 12. 3. 21:06

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


역시 최단경로 기본문제이다.

한 점에서 다른 점으로 도달하는데 가중치가 있고 최소비용을 구해야 한다면 Dijkstra를 고려하자.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <queue>
#define MAX 1001
#define INF 1000000000
using namespace std;

int n, m, init, target;
struct City{
    int idx, dist = INF;
    vector<pair<int, int>> next;
    bool operator < (const City &c) const {
        return dist > c.dist;
    }
};
City city[MAX];

void dijkstra(){
    priority_queue<City> pq;
    pq.push(city[init]);
    while(!pq.empty()){
        City curCity = pq.top();
        pq.pop();
        for(pair<int, int> pa : curCity.next){
            if(city[pa.second].dist > curCity.dist + pa.first){
                city[pa.second].dist = curCity.dist + pa.first;
                pq.push(city[pa.second]);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        city[i].idx = i;
    }
    while(m--){
        int i, j, w;
        cin >> i >> j >> w;
        city[i].next.push_back(make_pair(w, j));

    }
    cin >> init >> target;
    city[init].dist = 0;
    dijkstra();
    cout << city[target].dist << '\n';
    return 0;
}


저작자표시 (새창열림)