BOJ 1916 : 최소비용 구하기 [C++]

문제

 

 

최단 거리 + 시간 제한 0.5초인걸 보고 다익스트라이지 않을까? 하고 다익스트라를 조졌더니

26%에서 시간 초과가 났다.

뭐가 문젠지 고민하다가 질문 검색탭을 보니(이 글),

출발 - 도착이 같은 경우가 있으면 priority_queue에 같은 노드가 여러번 들어가니,

간선 정보를 다 입력받고 각 노드에서 갈 수 있는 목적지를 비용 순으로 정렬해주면 된다고 한다.

평소에 스스로 반례를 찾아보는 경우가 잘 없는데, 아마 저런 생각은 반례를 찾다보면 생각나는게 아닐까 한다.

 

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

#define INF 2000000000

std::vector<std::pair<int, int>> edges[1001];
int dist[1001];

void dijkstra(int start) {
    dist[start] = 0;
    std::priority_queue<std::pair<int, int>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int cur_node = pq.top().second;
        int cur_dist = -pq.top().first;
        pq.pop();

        for (int i = 0; i < edges[cur_node].size(); i++) {
            int next_node = edges[cur_node][i].first;
            int next_dist = cur_dist + edges[cur_node][i].second;

            if (next_dist < dist[next_node]) {
                dist[next_node] = next_dist;
                pq.push({-next_dist, next_node});
            }
        }
    }
}

bool cmp(std::pair<int, int> a, std::pair<int, int> b) {
    return (a.second < b.second);
}

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

    int n = 0;
    std::cin >> n;

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

    int m = 0;
    std::cin >> m;
    for (int i = 0; i < m; i++) {
        int start = 0, end = 0, cost = 0;
        std::cin >> start >> end >> cost;
        edges[start].push_back({end, cost});
    }

    for (int i = 1; i < n + 1; i++) {
        std::sort(edges[i].begin(), edges[i].end(), cmp);
    }

    int start = 0, end = 0;
    std::cin >> start >> end;
    dijkstra(start);

    std::cout << dist[end] << "\n";

    return 0;
}