백준 1916 : 최소비용 구하기

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; }