BOJ 1197:最小生成ツリー

✔問題リンク

✔トラブルシューティングポリシー

✔解決過程

✔正解コード

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

using ti3 = tuple<int, int, int>;

// weight, vertex
vector<pair<int,int> > adj[10001];
bool vis[10001];

void prim(int v, int e);

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int v, e;
  cin >> v >> e;

  for(int i=0;i<e;i++) {
    int a, b, c; // v1, v2, weight
    cin >> a >> b >> c;
    adj[a].push_back({c,b});
    adj[b].push_back({c,a});
  }

  prim(v, e);
}

void prim(int v, int e) {
  int cnt = 0;
  int total = 0;
  priority_queue<ti3, vector<ti3>, greater<ti3> > pq;

  // start from v1
  for(auto cur : adj[1])
    pq.push({cur.first, 1, cur.second});

  vis[1] = 1;

  while(1) {
    int weight, v1, v2;
    tie(weight, v1,v2) = pq.top();
    pq.pop();

    // case 1: already in MST -> do nothing
    if(vis[v2]) continue;

    // case 2: include v2
    vis[v2]=1;
    total += weight;
    cnt++;

    if(cnt==v-1) break;
    for(auto cur : adj[v2]) {
      if(!vis[cur.second])
        pq.push({cur.first, v2, cur.second});
    }
  }
  cout << total;
}

	

✔正解コード

✔ Comment

priority_queue<int, vector<int>, greater<int>> pq;

✔参考資料