골랜디 #4 1753번

Published at: 2025-03-23

Last modified at: 2025-03-23

오늘 푼 문제

안녕하세요 한라나입니다.
면허는 무난하게 합격했습니다.
그래서 그런가 저녁 먹으면서 술을 좀 마셔서, 4일짼데 벌써 던질까 라는 생각이 들었습니다.
그래도 랜덤은 돌려봤는데요, 세상이 저를 한번 지켜주는것 같네요?

이 세상이 시뮬레이터 트루먼쇼 가상세계가 아닐수가 없습니다.
왜냐고요?

제가 문제 만들기 수행평가할때 같은 문제 냈거든요ㅋㅋㅋㅋ
아니 이게 어떻게 4트만에 나와ㅋㅋㅋㅋㅋ

정확히는 제가 만든 문제는 양방향 그래프고, 본 문제는 단방향 그래프입니다. 근데 입력단에서 한줄만 붙이고 떼고 하면 서로 코드가 호환이 돼요.

…이게 진짜 말이 되나?

암튼 제가 만든 문제는 링크 타고 가면 있습니다. 저도 라나나라에 사는 한라나가 되고 싶네요.

문제는 간단합니다. 다익스트라 알고리즘을 그대로 사용하는 문제인데, Priority Queue를 사용해서 출발점에서 간선으로 이어진 정점을 다 pq에 넣고, 거리를 저장하고, 그 다음부턴 현재 있는 정점에서 간선으로 이어진 정점을 다 pq에 넣은 다음에 구한 거리가 현재 저장되어있는 거리보다 짧으면 바꿔주고 하면서 다 보면 됩니다.

while (!pq.empty()) {
    int d = pq.top().first;
    int u = pq.top().second;
    pq.pop();
    
    if (d > dist[u]) continue;
    
    for (auto &edge : graph[u]) {
        int v = edge.first;
        int w = edge.second;
        
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.emplace(dist[v], v);
        }
    }
}

양방향 그래프일때와 단방향 그래프일때 코드가 어떻게 호환되냐면, 입력을 받을 때 양방향이면 graph[u]에 v를 추가하고 graph[v]에 u를 추가하면 되고, 단방향이면 전자만 하면 됩니다. 진짜 한줄 차이에요.

요즘 하늘에 감사하는 날이 많네요. 케이온 재상영이 저에게 오만가지 행운을 가져다 주는 걸지도 모르겠습니다.

감사합니다.

---

전체 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
const int INF = 2147483647;

int main() {
    int N, M, S;
    cin >> N >> M >> S;
    
    vector<vector<pair<int, int>>> graph(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
    }
    
    vector<int> dist(N + 1, INF);
    dist[S] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(0, S);
    
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto &edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    
    for (int i = 1; i <= N; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }
    
    return 0;
}

왜 iostream이 되었냐구요? ..옛날 코드라, 이때는 한번 iostream 써볼까 했었는데, 역시 저는 stdio가 마음이 편합니다. 어딜 근본도 없는 iostream따위가