글 읽기 - min_heap 안쓰고 풀수 있는 방법?

sedman 6년 전 0

안녕하세요.

priority_queue를 안쓰고 풀수 있는 방법이 잇을까요?

아래와 같이 해봤는데, 시간 초과가 납니다.; 각 정점의 K까지 확인해서 다음 갈 정점을 선택해야 하니

시간이 오래 걸리는것 같습니다. 혹시 여기서 최적화할수 있는 건 없을까요?

int dijkstra(const int nCity, const int nPave)
{
  dist[0][0] = 0;
  int cur_idx, cur_dist = INT_MAX;
  int step = 0;
  for(int idx = 0; idx < nCity*(nPave + 1); ++idx)
  {
    cur_dist = INT_MAX;
    for(int j = 0; j < nCity; ++j)
    {
      for(int i = 0; i <= nPave; ++i)
      {
        if(visited[j][i] == false && cur_dist > dist[j][i])
        {
          cur_dist = dist[j][i];
          cur_idx = j;
          step = i;
        }
      }
    }
    if(cur_dist == INT_MAX)
      break;
    visited[cur_idx][step] = true;
    auto list = adj_list[cur_idx];
    for(auto pair : list)
    {
      int to_idx = pair.first;
      int cost = pair.second;
      if(step + 1 <= nPave && dist[to_idx][step + 1] > dist[cur_idx][step])
      {
        dist[to_idx][step + 1] = dist[cur_idx][step];
      }
      if(dist[to_idx][step] > cur_dist + cost)
      {
        dist[to_idx][step] = cur_dist + cost;
      }
    }
  }
  int result = INT_MAX;
  for(int idx = 0; idx <= nPave; ++idx)
  {
    if(dist[nCity - 1][idx] < result)
      result = dist[nCity - 1][idx];
  }
  return result;
}

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

문제

문제

출처

ICPC

min_heap 안쓰고 풀수 있는 방법?

sedman 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말