글 읽기 - java 에서 틀렸다고 나오네요...

heyname 4년 전 0

60% 정도에서 틀렸다고 나오네요.

각 vertex마다 edge를 list로 연결해서 관리하고, 매번 가장 짧은 거리를 찾을 때마다 모든 vertex를 다 돌아다니도록 해놔서... V²으로 시간초과가 날 수는 있다고 생각하는데.. 60%에서 왜 틀린지 잘 모르겠네요. min heap을 이용해서 하나씩 찾아서 queue에 집어넣는 방식이 빠를 것 같긴 한데.. language에서 지원하는 자료구조 없이 간단히 구현해볼려고 했는데.. 어디가 오류가 있는지 잘 모르겠네요..

import java.util.Scanner;

class Node {
  public int index = 0;
  public int cost = 0;
  public Node next = null;

  public Node(int index, int cost) {
    this.index = index;
    this.cost = cost;
  }
}

class Graph {
  public static final int MAX = 20001;
  public Node[] nodes = new Node[MAX];

  public void addEdge(int s, int e, int c) {
    Node newNode = new Node(e, c);
    newNode.next = nodes[s].next;
    nodes[s].next = newNode;
  }
}

public class Main {
  static int N = 0;
  static boolean[] visited = new boolean[Graph.MAX];
  static int[] answer = new int[Graph.MAX];

  private static int getNextMinNode() {
    int min = Integer.MAX_VALUE;
    int nodeIndex = -1;
    for(int i = 1; i <= N; ++i) {
      if(!visited[i] && answer[i] < min) {
        min = answer[i];
        nodeIndex = i;
      }
    }
    
//    System.out.println("getNextMinNode() " + nodeIndex);

    return nodeIndex;
  }

  private static void solve(int start, Graph graph) {
    int target = 0;
    while((target = getNextMinNode()) != -1) {
      visited[target] = true;
      
//      System.out.println("target " + target);

      Node targetNode = graph.nodes[target];
      int costToTarget = answer[target];
      Node adjNode = targetNode.next;
      while(adjNode != null) {
        if(!visited[adjNode.index] && (costToTarget+adjNode.cost) < answer[adjNode.index]) {
          answer[adjNode.index] = costToTarget+adjNode.cost;
          
//          System.out.println("updated " + adjNode.index  + " " + answer[adjNode.index]);
        }

        adjNode = adjNode.next;
      }
    }
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    N = scanner.nextInt();
    int E = scanner.nextInt();
    int start = scanner.nextInt();

    Graph graph = new Graph();
    for(int i = 1; i <= N; ++i) {
      answer[i] = Integer.MAX_VALUE;
      graph.nodes[i] = new Node(i, 0);
    }

    
    for(int i = 0; i < E; ++i) {
      int u = scanner.nextInt();
      int v = scanner.nextInt();
      int w = scanner.nextInt();
      
      if(u == start) {
        answer[v] = w;
      }

      graph.addEdge(u, v, w);
    }
    
    visited[start] = true;
    solve(start, graph);

    for(int i = 1; i <= N; ++i) {
      if(i == start) {
        System.out.println("0");
      } else {
        if(answer[i] == Integer.MAX_VALUE) {
          System.out.println("INF");
        } else {
          System.out.println(answer[i]);
        }
      }
    }
  }
}

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

문제

문제

출처

ICPC

java 에서 틀렸다고 나오네요...

heyname 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말