글 읽기 - C 어디에서 틀린지 모르겠습니다.

jakeehoson 3년 전 0

일단 틀렸습니다.

어디서 틀렸는지는 모르겠습니다.

그리고 추가적으로 문제의 '여러개의 간선이 있을 수 있다'는 것이 동일한 노드에서 동일한 노드로 가는 간선이 여러 개 있을 수 있다는 말인가요?

그렇게 이해하고 가장 짧은 간선만 저장하게 해두었습니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define MAX_V 20001
#define MAX_E 300001

int vertex_num, edge_num, start_point;
int u, v, w;
int* dist, * visit;

struct edge{
  int to;
  int weight;
};

struct vertex{
  int index;
  int count;
  struct edge* edges;
};
struct vertex vertexes[MAX_V];

struct heap{
  int que[MAX_E];
  int size;
}heap;

int min(int a, int b);
int heap_pop();
void heap_push(int index);

int main()
{
  scanf("%d %d\n%d", &vertex_num, &edge_num, &start_point);
 
  for (int i = 1; i <= vertex_num; i++){
    vertexes[i].index = i;
    vertexes[i].edges = (struct edge*)malloc(sizeof(0));
    vertexes[i].count = 0;
  }
  bool exists;
  for (int i = 0; i < edge_num; i++){
    exists = false;
    scanf("%d %d %d", &u, &v, &w);
    for (int e = 0; e < vertexes[u].count; e++){
      if (vertexes[u].edges[e].to == v){
        if (vertexes[u].edges[e].weight > w){
          vertexes[u].edges[e].weight = w;
        }
        exists = true;
        break;
      }
    }
    if (!exists){
      vertexes[u].edges = (struct edge*)realloc(vertexes[u].edges, sizeof(struct edge) * (vertexes[u].count + 1));
      vertexes[u].edges[vertexes[u].count].to = v;
      vertexes[u].edges[vertexes[u].count].weight = w;;
      vertexes[u].count++;
    }
  }

  dist = (int*)malloc(sizeof(int) * (vertex_num + 1));
  visit = (int*)malloc(sizeof(int) * (vertex_num + 1));

  for (int i = 1; i <= vertex_num; i++){
    dist[i] = INT_MAX;
    visit[i] = 0;
  }
  
  dist[start_point] = 0;
  heap_push(start_point);
  while(heap.size > 0){
    int index = heap_pop();    
    if (visit[index] == 1){
      continue;
    }
    visit[index] = 1;
    for (int e = 0; e < vertexes[index].count; e++){
      struct edge e_now = vertexes[index].edges[e];
      dist[e_now.to] = min(dist[e_now.to], dist[index] + e_now.weight);
      if (visit[e_now.to] == 0){
        heap_push(e_now.to);
      }
    }
  }
  for (int i = 1; i <= vertex_num; i++){
    if (dist[i] == INT_MAX){
      printf("INF\n");
    }else{
      printf("%d\n", dist[i]);
    }
  }
  return 0;
}
int heap_pop(){
  int index = heap.que[0];
  heap.size--;
  if (heap.size == 0){
    return index;
  }
  heap.que[0] = heap.que[heap.size];

  int temp;
  int parent = 0, child = 1;

  while(child <= heap.size - 1){

    if (heap.size > child && dist[heap.que[parent * 2 + 1]] > dist[heap.que[parent * 2 + 2]]){
      child++;
    }
    if (dist[heap.que[parent]] > dist[heap.que[child]]){
      temp = heap.que[parent];
      heap.que[parent] = heap.que[child];
      heap.que[child] = temp;

      parent = child;
      child = child * 2 + 1;
    }else{
      break;
    }
  }
  return index;
}
void heap_push(int index){
  int now = heap.size;
  heap.size++;
  while(now != 0){
    if (dist[index] < dist[heap.que[(now - 1) / 2]]){
      heap.que[now] = heap.que[(now - 1) / 2];
      now = (now - 1) / 2;
    }else{
      break;
    }
  }
  heap.que[now] = index;
}
int min(int a, int b){
  if (a > b){
    return b;
  }else{
    return a;
  }
}

jakeehoson 3년 전 1

해결했습니다. 가중치가 제일 낮은 간선부터 방문하는 실수를 하고 있었습니다.

https://www.acmicpc.net/board/...

위 글을 참고하시면 도움 될 듯합니다.

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

문제

문제

출처

ICPC

C 어디에서 틀린지 모르겠습니다.

jakeehoson 3년 전 0

jakeehoson 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말