글 읽기 - 1922 왜 틀렸는지 조르겠습니다 ㅜㅜ

joehandlebar 5년 전 0

Prim's로 구현해봤는데 틀렸어요 ㅠㅠ 어디가 잘못된 걸까요 ??

#include <iostream>
#include <cstdio>
#include <unordered_set>
#include <queue>
#include <vector>

using namespace std;

long long W[1009][1009];
long long INF = 6223372036854775807;
long long keys[1009];

struct LessThanByKey {
  bool operator() (int i, int j) {
    return keys[i] > keys[j];
  }
};

void prims(int N, vector<vector<int>> adj) {
  priority_queue<int,vector<int>,LessThanByKey> Q;
  unordered_set<int> S;
  fill_n(begin(keys),N+1,INF);
  Q.push(1);
  keys[1] = 0;

  while (!Q.empty()) {
    int j = Q.top();
    Q.pop();

    S.insert(j);
    vector<int> v = adj[j];
    auto it = v.begin();

    while (it != v.end()) {
      if (S.find(*it) == S.end() && W[j][*it] < keys[*it]) {
        keys[*it] = W[j][*it];
        Q.push(*it);
      }
      it++;
    }
  }
}

int main() {
  int N, M, a, b; long long c;
  scanf("%d %d", &N, &M);

  vector<vector<int>> adj(N+1);
  for (int i = 1; i <= M; i++) {
    scanf("%d %d %lld", &a, &b, &c);
    adj[a].push_back(b); W[a][b] = c;
    adj[b].push_back(a); W[b][a] = c;
  }
  prims(N, adj);

  long long cost = 0;
  for (int i = 1; i <= N; i++) { cost += keys[i]; }
  cout << cost << '\n';

  return 0;
}

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

문제

문제

출처

ICPC

1922 왜 틀렸는지 조르겠습니다 ㅜㅜ

joehandlebar 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말