글 읽기 - 시간초과

akswnd98 3년 전 0

908ms로 겨우 통과한 코드입니다.

edge개수가 4백만인 그래프라고 보기엔 시간이 너무 오래걸린 것 같습니다.

제가 다익스트라 알고리즘(ElogV)을 잘못 구현했거나 최적화에 실패한거 같은데, 시간을 줄이려면 어디를 수정해야 될까요?

#include <bits/stdc++.h>
using namespace std;

#define forn(i, init, fin) for(i = init; i < fin; i++)

typedef long long int64;
class tri {
public:
  int x, y, z;
  tri(int x, int y, int z)
  : x(x), y(y), z(z) { }
  tri(const tri &q)
  : x(q.x), y(q.y), z(q.z) { }
};
typedef vector<tri> vt;
typedef list<tri> lt;
typedef vector<lt> vlt;
class tri_cmp {
public:
  bool operator()(const tri &a, const tri &b) {
    return a.z > b.z;
  }
};
typedef priority_queue<tri, vt, tri_cmp> p_qt;

int K, N, M;
int A, B;
vlt G;
int dp[2005][205];
vt cont;
p_qt pq(tri_cmp(), cont);

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int i, j, k;

  cont.reserve(16000050);

  cin >> K >> N >> M;
  G.resize(N + 1);
  forn(i, 0, M) {
    int a, b, t, h;
    cin >> a >> b >> t >> h;
    G[a].push_back(tri(b, t, h));
    G[b].push_back(tri(a, t, h));
  }
  cin >> A >> B;
  forn(i, 0, 2005) {
    forn(j, 0, 205) {
      dp[i][j] = 1e9;
    }
  }
  pq.push(tri(A, 0, 0));
  while(!pq.empty()) {
    tri cur = pq.top();
    pq.pop();
    if(dp[cur.x][cur.y] <= cur.z) continue;
    dp[cur.x][cur.y] = cur.z;
    for(lt::iterator it = G[cur.x].begin(); it != G[cur.x].end(); it++) {
      if(cur.y + it->z >= 205) continue;
      pq.push(tri(it->x, cur.y + it->z, cur.z + it->y));
    }
  }
  int rst = 1e9;
  forn(i, 0, K) {
    rst = min(rst, dp[B][i]);
  }
  if(rst >= 1e9) cout << -1 << '\n';
  else cout << rst << '\n';

  return 0;
}

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

문제

문제

출처

ICPC

시간초과

akswnd98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말