[백준/C++] #14284 간선 이어가기 2 (Dijsktra)

문제

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

배열 크기 잘못설정해서 메모리 초과가 났엇다..ㅎ

 

풀이

간선 정보들 연결리스트로 관리하고, 최단 경로 길이 배열에 저장하고, 최단 경로 구할때 시간복잡도 줄이기 위해 우선순위 큐를 쓰는.. 가장 전형적인 다익스트라 문제였다.

다익스트라 문제들은 거의 풀이 형태가 같으니 한번 제대로 익혀놓는걸 추천한다!

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
/*
특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것
s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되도록 추가하는 간선의 순서를 조정
-> 최솟값은? 
*/

int n; // 정점의 개수
int m; // 간선 리스트의 수
int s, t;
vector<pair<int, int>> v[5001]; // 연결리스트
int d[5001]; // 최단 경로 길이

void solution() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 오름차순 정렬
    pq.push({ 0, s }); // 거리는 0, 노드 s에서 출발
    d[s] = 0; // 시작점까지의 거리는 0

    while (!pq.empty()) {
        pair<int, int> now = pq.top();
        int distance = now.first;
        int curr_node = now.second;
        pq.pop();

        if (d[curr_node] < distance) continue; // 최적의 상황이 아님

        for (int i = 0; i < v[curr_node].size(); i++) {
            int next_distance = distance + v[curr_node][i].second;
            int next_node = v[curr_node][i].first;

            if (next_distance < d[next_node]) { // 갱신
                d[next_node] = next_distance;
                pq.push({ d[next_node], next_node });
            }
        }

    }
}

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

    // 입력
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b, c });
        v[b].push_back({ a, c }); // 무 방향 연결 그래프
    }
    cin >> s >> t;

  
    // 로직

    // 경로 길이 초기화
    for (int i = 0; i <= n; i++) {
        d[i] = INF;
    }

    // 결과 계산
    solution();

    // 출력
    if (d[t] == INF) {
        cout << "-1";
    }
    else {
        cout << d[t];
    }

    return 0;
}