[백준/C++] 1753번 최단경로

백준

---

🤔문제 이해

시작점에서 각 정점을 방문하기 위해 필요한 최소 비용을 구하는 문제이다.

---

💡첫번째 아이디어

문제가 그냥 딱 다익스트라 문제라 다익스트라를 이용했다.

 

🔥풀이🔥

다익스트라를 그대로 구현하였고, 다음 정점까지의 거리를 우선순위큐에 넣어주기 전에 이미 그 정점까지 최소거리보다 크면 큐에 넣어주지 않고 continue를 해주었다. 그리고 우선순위큐에 들어있는 정점이 이미 최소거리가 확정되었다면 그 때에도 continue를 해줘서 불필요한 연산을 줄여주었다. 

 

---

아래는 제출한 코드이다.

#include <iostream>
#include <queue>

using namespace std;
#define INF 100000000

int dist[20002], v, e, k;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> v >> e >> k;

    vector<vector<pair<int, int>>> edge(v+1);
    int a, b, c;
    for (int i = 0; i < e; i++) {
        cin >> a >> b >> c;
        edge[a].push_back({b, c});
    }

    for (int i = 1; i <= v; i++) {
        dist[i] = INF;
    }
    dist[k] = 0;

    priority_queue<pair<int, int>> pq;

    pq.push({0, k});

    while (!pq.empty()) {
        int weight = -pq.top().first;
        int vertex = pq.top().second;
        pq.pop();
        if (weight > dist[vertex])
            continue;

        for (auto u: edge[vertex]) {
            int n = u.first;
            int w = u.second + weight;
            if (dist[n] <= w) continue;
            pq.push({-w, n});
            dist[n] = w;
        }
    }

    for (int i = 1; i <= v; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }
}