1753번: 최단경로 (백준 온라인 저지, C++)

문제 풀이

 

priority queue를 이용한 다익스트라 알고리즘을 사용하는 문제입니다. 노드의 수가 매우 많기 때문에 메모리를 줄이기 위하여 간선을 저장하였습니다. 단방향 그래프이기 때문에, 출발 노드와 도착 노드 중 출발 노드에만 간선을 저장해 주었습니다. check 배열에는 해당 노드를 방문한 적이 있는지 알아보았고, road 배열에는 최단 거리를 저장해주었습니다. 재방문하게 되는 경우, 최단 거리를 갱신하면서 탐색을 진행합니다.

다익스트라 알고리즘에 대해서 반드시 알아야 풀 수 있었던 문제라, 한 번 알아보시면 도움이 될 것 같습니다!

 

 

코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <utility>
 
using namespace std;
 
const int MAX = 999999;
 
int ans;
bool check[20001];
int road[20001];
vector <pair<int, int>> g[20001];
 
void bfs(int a) {
 
    memset(check, false, sizeof(check));
    memset(road, MAX, sizeof(road));
    priority_queue <pair<int, int>, vector< pair<int,int> >, greater< pair<int, int> > > q;
    q.emplace(0, a);
    road[a] = 0;
    check[a] = true;
 
    while (!q.empty()) {
        pair<int, int> x;
        x = q.top();
        q.pop();
 
        for (int i = 0; i < g[x.second].size(); i++) {
            if (check[g[x.second][i].first] == false || road[g[x.second][i].first] > x.first + g[x.second][i].second)
            {
                check[g[x.second][i].first] = true;
                road[g[x.second][i].first] = x.first + g[x.second][i].second;
                q.emplace(x.first + g[x.second][i].second, g[x.second][i].first);
            }
        }
    }
}
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, e, s;
    cin >> n >> e >> s;
 
    for (int i = 1; i <= e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
    }
 
    bfs(s);
 
    for (int k = 1; k <= n; k++) {
        
        if (!check[k])
            cout << "INF\n";
        else
            cout << road[k] << '\n';
    }
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

1753번: 최단경로