leetcode-go/poj/1258.agri-net/main.cc

#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <vector>

using namespace std;

const int N = 100;
const int INF = 0x3F3F3F3F;

int dist[N];

struct E {
  int v;
  int w;
  E(int v = 0, int w = INF) : v(v), w(w) {}
  bool operator<(const E &that) const { return this->w > that.w; }
};

int main() {
  int n, len, used;
  while (scanf("%d", &n) != EOF) {
    vector<vector<E>> adj;
    for (int i = 0, w; i < n; i++) {
      adj.push_back(vector<E>());
      for (int j = 0; j < n; j++) {
        scanf("%d", &w);
        adj[i].push_back(E(j, w));
      }
    }
    memset(dist, 0x3F, sizeof(dist));
    dist[0] = 0, len = 0, used = 1;
    priority_queue<E> pq;
    for (int i = 0; i < adj[0].size(); i++) pq.push(adj[0][i]);
    while (used != n) {
      E e;
      do {
        e = pq.top();
        pq.pop();
      } while (dist[e.v] != INF);
      dist[e.v] = e.w;
      len += e.w;
      used++;
      for (int i = 0; i < adj[e.v].size(); i++) {
        E &u = adj[e.v][i];
        if (dist[u.v] == INF) pq.push(u);
      }
    }
    printf("%d\n", len);
  }
  return 0;
}