글 읽기 - 이 풀이가 틀린 이유를 모르겠습니다.

shadowpur97 2년 전 1

다익스트라로 풀었는데, 조금 다른 방향으로 시도해봤는데 계속 틀리게 나오더라구요.

보통 다익스트라로 풀 때 priority_queue를 쓰고, queue에 집어넣을 떄 {거리, 노드} 이렇게 넣고 돌립니다.

근데 저는 {노드}만 집어넣고, queue의 compare 방법을 실시간 dist[] 배열의 값을 비교하는 것으로 바꿨습니다.

이렇게 풀면 이미 방문한 노드를 재방문할 때 계속해서 다시 체크해야 한다는 시간적인 단점이 있는데, 시간초과도 아니고 틀렸다고 나오더라구요.

혹시 이유를 아시는 분 있을까요?

#include <iostream>
#include <memory.h>
#include <limits.h>
#include <cmath>
#include <queue>
using namespace std;

int N, M, X;

int map[1000][1000];
int dist[1000];

struct compare
{
  bool operator()(int a, int b)
  {
    return dist[a] > dist[b];
  }
};

priority_queue<int, vector<int>, compare> search;

int main()
{
  memset(map, 0x0f, sizeof(map));
  cin >> N >> M >> X;

  for(int mdx = 0; mdx < M; mdx++)
  {
    int src, dst, len;
    cin >> src >> dst >> len;
    map[src-1][dst-1] = len;
  }

  for(int rdx = 0; rdx < N; rdx++)
    map[rdx][rdx] = 0;

  int max_time = 0;

  for(int ndx = 0; ndx < N; ndx++)
  {
    search.push(ndx);
    memset(dist, 0x0f, sizeof(dist));
    dist[ndx] = 0;

    while(!search.empty())
    {
      int curr = search.top();
      search.pop();

      if(curr == X-1)
        break;

      for(int rdx = 0; rdx < N; rdx++)
      {
        if(curr == rdx)
          continue;

        if(map[curr][rdx] + dist[curr] < dist[rdx])
        {
          search.push(rdx);
          dist[rdx] = map[curr][rdx] + dist[curr];
        }
      }
    }

    while(!search.empty())
      search.pop();

    int a = dist[X-1];

    search.push(X-1);
    memset(dist, 0x0f, sizeof(dist));
    dist[X-1] = 0;

    while(!search.empty())
    {
      int curr = search.top();
      search.pop();

      if(curr == ndx)
        break;

      for(int rdx = 0; rdx < N; rdx++)
      {
        if(curr == rdx)
          continue;

        if(map[curr][rdx] + dist[curr] < dist[rdx])
        {
          search.push(rdx);
          dist[rdx] = map[curr][rdx] + dist[curr];
        }
      }
    }

    while(!search.empty())
      search.pop();

    int b = dist[ndx];



    max_time = max(max_time, a + b);
  }

  cout << max_time;
}

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

문제

문제

출처

ICPC

이 풀이가 틀린 이유를 모르겠습니다.

shadowpur97 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말