[c++] BOJ 1753 :: 최단경로

난이도 : 골드 5

걸린 시간 : 1시간 반 이상 (오류 찾기)

 

문제

최단경로 문제 바로가기

 

풀이

• 다익스트라 기본 구현을 이용해서 푼다.
• 다익스트라 개념 바로가기

---

코드

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

using namespace std;

int main() {
    // 입력
    // v, e는 10^5, 10^6이하
    int V; int E;
    cin >> V >> E;
    int start; // 시작 정점
    cin >> start;

    vector<vector<pair<int, int>>> edge(V+1, vector<pair<int,int>>(0));

    for (int i = 0; i < E; i++) { //10^6
        int from; int to; int val;
        cin >> from >> to >> val;
        edge[from].push_back(make_pair(to, val));
    }

    vector<int> memo(V+1, 1e9);
    vector<int> visited(V + 1, 0);
    priority_queue<pair<int, int>> que; // 주변 노드에 대한 간선의 크기 유지 (val, to)
    memo[start] = 0;
    que.push(make_pair(0,start));

    while (que.size()!=0) {
        auto node = que.top(); que.pop(); // 가장 가중치 낮은 아이 데려오기
        int val = -node.first; int from = node.second;
        if (visited[from]!=0) { // 이미 tree에 포함된 노드이면 다시 하지 x
            continue;
        }
        visited[from] = 1;

        auto nodeEdge = edge[from];
        for (int i = 0; i < nodeEdge.size(); i++) {
            int to = nodeEdge[i].first; int val2 = nodeEdge[i].second;
            if (memo[to] > memo[from] + val2) {
                memo[to] = memo[from] + val2;
                que.push(make_pair(-memo[to], to)); // -로 집어넣어서 최소값이 나오게 하기
            }
        }
    }

    for (int i = 1; i < V+1; i++) {
        if (memo[i] == 1e9) {
            cout << "INF";
        }
        else {
            cout << memo[i];
        }
        cout << '\n'; // 여기를 endl로 하면 시간 초과..
    }
}

 

결과

마지막 출력 시 endl을 사용하면 시간초과가 뜬다. '\n'을 사용하자..

백준 judge는 입출력 시간도 포함하며 endl은 출력버퍼를 비워야해서 느리다고 한다.