글 읽기 - C++ 시간 초과가 나는데 이유를 모르겠네요.. 어디가 잘못된 걸까요?

cosgenio 2년 전 0

노드는 간선들을 가지고 있고, 이러한 노드를 저장하는 vector를 만들었습니다

시작 점을 큐에 넣고 가리키는 노드들을 순회하면서 순회 안된거면 거리 갱신 진행하고 큐에 넣고, 순회 된거면 패스하고, 다 하면 큐에서 빼는 식으로 계산하는데 자꾸 시간 초과가 나오네요

이유좀 알려주세요 ㅠㅠ

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

struct Vertex {
  Vertex() = default;
  Vertex(int n, int w) : to(n), weight(w) {}
  int to;
  int weight;
};

std::vector<int> dijkstra(const std::vector<std::vector<Vertex>>& graph, int start) {
  std::vector<int> shorts(graph.size(), std::numeric_limits<int>::max());
  shorts[start] = 0;

  std::vector<bool> visited(graph.size(), false);
  std::queue<int> will_visit;
  will_visit.push(start);

  while (!will_visit.empty()) {
    const auto from = will_visit.front();
    will_visit.pop();

    for (const auto& vertex : graph[from]) {
      if (visited[vertex.to]) continue;
      shorts[vertex.to] = std::min(shorts[vertex.to], shorts[from] + vertex.weight);
      will_visit.push(vertex.to);
    }
    visited[from] = true;
  }

  return shorts;
}

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

  int V, E, K;

  std::cin >> V >> E;
  std::cin >> K;

  std::vector<std::vector<Vertex>> nodes(V + 1);

  for (int i = 0, n1, n2, w; i < E; ++i) {
    std::cin >> n1 >> n2 >> w;
    nodes[n1].emplace_back(n2, w);
  }

  const auto result = dijkstra(nodes, K);

  for (int i = 1; i < result.size(); ++i) {
    if (result[i] > 10)
      std::cout << "INF\n";
    else
      std::cout << result[i] << '\n';
  }

}

djm03178 2년 전 0

다익스트라는 큐에서 뽑을 때 현재까지 거리가 최단인 정점을 뽑아야 합니다. 일반적인 큐로는 달성할 수 없으며, 우선순위 큐를 써야 하는 이유가 그것입니다.

일반 큐를 쓰는 기법도 존재하지만 그건 다익스트라라고 부르지 않으며 SPFA라는 별도의 이름이 있습니다. 그러나 SPFA가 되려면 어떤 정점이 큐에 이미 들어가 있다면 다시 큐에 넣지 않아야 할 뿐만 아니라, 평균적인 경우에서 빠를 뿐 최악의 케이스에서는 매우 느리고 이 문제 역시 저격 데이터가 들어가 있어 통과될 수 없습니다.

cosgenio 2년 전 0

아아 맞네요! 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ 시간 초과가 나는데 이유를 모르겠네요.. 어디가 잘못된 걸까요?

cosgenio 2년 전 0

djm03178 2년 전 0

cosgenio 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말