[BOJ] 최단 경로

[문제]

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

1753번: 최단경로

[풀이]

1753

맞았습니다!!

15732

108

C++14 / 수정

1763

2분 전

 

1) 하나의 정점에서 다른 모든 정점으로 가는 최단 경로 (== 다익스트라 알고리즘을 써라)

 

2) 다익스트라 함수를 호출하기 전에 시작점을 제외한 모든 간선의 가중치를 INF로 설정한다. 

 

3) 다익스트라 함수 (시작점, 비용)을 호출하고 우선순위큐를 생성한다. 

우선순위 큐에 가중치를 먼저 삽입해서 비용을 기준으로 오름차순으로 정렬되어 나올 수 있도록 한다. 

오름차순 -> priority_queue<pair<int, int> , vector<pair<int, int>>, greater<int, int>> 

==> #include <functional > 필요 

 

4) 큐에서 나온 값들은 최단 경로 가중치로 고정된다. (visited를 통해 적절히 거른다)

 

5) 최소 가중치를 가진 정점에 연결된 간선의 가중치를 살펴보면서 최소 가중치를 가진 간선을 큐에 넣는다. 

 

---

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
 
#define MAX_E 300001
#define MAX_V 20001
#define INF 987654321
using namespace std;
 
//최단 경로 : 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 
//단, 모든 간선의 가중치는 10 이하의 자연수이다. ===> 다익스트라 
int v, e;
typedef pair<int, int> pp;
int res[MAX_V]; //간선의 가중치를 저장 
vector<pp> edges[MAX_E];
bool visited[MAX_V];
 
void dijstra(int start, int cost) {
    priority_queue<pp, vector<pp>, greater<pp> > pq;
    pq.push(pp(cost, start)); //비용을 기준으로 오름차순
 
    while(!pq.empty()) {
        pp now = pq.top(); pq.pop();
 
        if (visited[now.second]) continue; //방문한 노드는 필요없음 (큐에서 나온 최단 경로는 고정 -> 다익스트라의 장점이자 단점 )
 
        visited[now.second] = true;
 
        for (auto i : edges[now.second]) {
            //해당 간선과 연결된 간선들의 가중치를 계산 
            int n_cost = i.first;
            int next = i.second;
 
            if (!visited[next] && res[next] > now.first + n_cost) {
                res[next] = now.first + n_cost;
                pq.push(pp(res[next], next));
            }
        }    
    }
 }
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> v >> e;
 
    int start;
    cin >> start;
 
    for (int i = 0; i < e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back(pp(w, v));
 
    }
    //input 
 
    for (int i = 1; i <= v; i++) {
        res[i] = INF;
    }
 
    res[start] = 0; //시작점의 가중치는 0
 
    dijstra(start, 0);
 
    for (int i = 1; i <= v; i++ ) 
    {
        if (visited[i]) {
            //최단 경로를 구성하는 원소 
            cout << res[i] << '\n';
        }
        else cout << "INF" << '\n';
    }
    return 0;
}