글 읽기 - JS로 푸는데 시간초과를 해결 할 수 가 없뜹니다..ㅜㅜ

kgc0517 6년 전 0

다익스트라로 문제를 풀었습니다.

dist[i][j] = i번째 도시를 j비용을 사용하여 도착한 시간.

1번부터 81은 우선순위큐 구현 코드이구 123줄 부터 다익스트라 코드 입니다.

var PriorityQueue = (function() {
  function PriorityQueue(data, compare) {
    this.data = data || [];
    this.length = this.data.length;
    this.compare = compare || defaultCompare;

    if (this.length > 0) {
      for (var i = (this.length >> 1) - 1; i >= 0; i--)
        this._down(i);
    }
  }

  function defaultCompare(a, b) {
    return a.time - b.time;
  }
  PriorityQueue.prototype = {
    push: function(item) {
      this.data.push(item);
      this.length++;
      this._up(this.length - 1);
    },
    pop: function() {
      if (this.length === 0)
        return undefined;

      var top = this.data[0];
      this.length--;

      if (this.length > 0) {
        this.data[0] = this.data[this.length];
        this._down(0);
      }
      this.data.pop();

      return top;
    },
    peek: function() {
      return this.data[0];
    },
    _up: function(pos) {
      var data = this.data;
      var compare = this.compare;
      var item = data[pos];

      while (pos > 0) {
        var parent = (pos - 1) >> 1;
        var current = data[parent];
        if (compare(item, current) >= 0)
          break;
        data[pos] = current;
        pos = parent;
      }
      data[pos] = item;
    },
    _down: function(pos) {
      var data = this.data;
      var compare = this.compare;
      var halfLength = this.length >> 1;
      var item = data[pos];

      while (pos < halfLength) {
        var left = (pos << 1) + 1;
        var right = left + 1;
        var best = data[left];

        if (right < this.length && compare(data[right], best) < 0) {
          left = right;
          best = data[right];
        }
        if (compare(best, item) >= 0)
          break;

        data[pos] = best;
        pos = left;
      }
      data[pos] = item;
    }
  };

  return PriorityQueue;
})();

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin', 'utf8').split('\n');
var idx = 0;
var test = parseInt(input[idx++]);

while (test--) {
  var tmp = input[idx++].split(' ');
  var V = parseInt(tmp[0]);
  var E = parseInt(tmp[2]);
  var K = parseInt(tmp[1]);
  var adj = [];
  for (var i = 0; i <= V; i++) {
    adj.push([]);
  }
  for (var i = 0; i < E; i++) {
    tmp = input[idx++].split(' ');
    adj[tmp[0]].push({
      to: parseInt(tmp[1]),
      cost: parseInt(tmp[2]),
      time: parseInt(tmp[3]),
    });
  }

  var dist = []
  for (var i = 0; i <= V; i++) {
    var tmp = [];
    for (var j = 0; j <= K; j++) {
     tmp.push(Infinity);
    }
    dist.push(tmp);
  }
  dist[1][0] = 0;

  var pq = new PriorityQueue();
  pq.push({
    from: 1,
    cost: 0,
    time: 0
  });
    //다익스트라
  while (pq.peek()) {
    var c = pq.pop();
    if(c.time > dist[c.from][c.cost]) continue;
    for (var i = 0; i < adj[c.from].length; i++) {
      var to = adj[c.from][i].to;
      var cost = adj[c.from][i].cost;
      var time = adj[c.from][i].time;

      if (c.cost + cost <= K && dist[to][c.cost + cost] > c.time + time) {
        dist[to][c.cost + cost] =  c.time + time
        pq.push({
          from: to,
          cost: c.cost + cost,
          time: c.time + time
        });
      }
    }
  }
  var ans = Infinity;
  for (var i = 0; i < K; i++) {
    ans = Math.min(ans, dist[V][i]);
  }
  console.log(ans===Infinity?'Poor KCM':ans);
}

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

문제

문제

출처

ICPC

JS로 푸는데 시간초과를 해결 할 수 가 없뜹니다..ㅜㅜ

kgc0517 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말