문제 : http://acmicpc.net/proble/1916
해당 문제는 다익스트라 알고리즘을 이용해서 구해야하는 방법이다.
다익스트라에 대한 설명은 해당 링크를 참조해주시기를 바랍니다.
여기서는 우선순위 큐를 이용해서 다익스트라 알고리즘을 구현하였습니다.
우선순위 큐는 큐의 최소값이 가장 우선되면서 pop이 됩니다.
그렇기 때문에 해당 알고리즘은 값을 넣을때 음수로 저장하고 다시 꺼낼때도 음수로 나오게 됩니다.
값의 저장 pq.push(make_pair(-neighbor_dist, neighbor));
값의 이용 int cost = -pq.top().first;
// ConsoleApplication2.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다. // #include <iostream> #include <cstdio> #include <queue> #include <vector> #include <algorithm> //필요는 없으나 습관 #include <limits.h> //INT_MAX 값을 불러오기 위함. #define NODE_MAX 1001 using namespace std; typedef pair<int, int> pii; int n, m; vector<pii> graph[NODE_MAX]; vector<int> dijkstra(int start) { //자기 자신을 가리키면 비용은 0 vector<int> dist(n, INT_MAX); dist[start] = 0; /* 시작할때 cost의 가중치가 없어야하고 어느 노드에 대해서 값을 구할 것인지 결정해야함 그래서 파라미터 0, start 들어감. */ priority_queue<pii> pq; pq.push(make_pair(0, start)); while (!pq.empty()) { /* 우선순위 큐에서 가장 작은 값이 가장 먼저 나오기 때문에 음수로 저장하고 꺼낼때 음수를 사용한다. */ int cost = -pq.top().first; // 현재 노드까지의 가중치값 int cur_vertex = pq.top().second; // 현재 노드 pq.pop(); /* 새로운 cost의 가중치가 기존 가중치보다 크다면 생략. */ if (dist[cur_vertex] < cost) continue; /* cur_vertex 노드와 인접 노드간의 가중치를 모두 구하기 위함. */ for (int i = 0; i < graph[cur_vertex].size(); i++) { /* neighbor = 인접 노드 neighbor_dist = 이전 노드까지의 가중치 최소값을 뜻하는 cost + 현재 인접노드[i] 가중치를 더한 값. */ int neighbor = graph[cur_vertex][i].first; int neighbor_dist = cost + graph[cur_vertex][i].second; /* 기존에 저장된 인접노드까지의 가중치가 클 경우 새롭게 갱신 */ if (dist[neighbor] > neighbor_dist) { dist[neighbor] = neighbor_dist; // 갱신. pq.push(make_pair(-neighbor_dist, neighbor)); //우선순위큐이기 때문에 가중치 값을 음수로 저장. } } } return dist; } int main(void) { cin >> n >> m; n++; // 값의 시작은 1부터이기 때문에. for (int i = 0; i < m; i++) { int from, to, val; cin >> from >> to >> val; graph[from].push_back(make_pair(to, val)); } int from, to; cin >> from >> to; //시작점 from에서 갈 수 있는 모든 노드의 가중치 값을 result에 저장하고 목적지 to의 값을 불러옴. vector<int> result(dijkstra(from)); cout << result[to] << endl; return 0; }
'알고리즘' 카테고리의 다른 글
| 백준 (DFS) 1697번 - 숨바꼭질 (0) | 2018.10.19 |
|---|---|
| 백준 (DFS) 9466번 - 텀 프로젝트 (0) | 2018.10.19 |
| 백준 (DFS) 2667번 - 단지번호붙이기 (0) | 2018.10.18 |
| 백준 (DFS) 10026번 - 적록색약 (0) | 2018.10.18 |