概要
最小全域木を求める.
typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; bool operator< (const Edge &a, const Edge &b){ return a.weight > b.weight; } pair<Weight, Edges> prim(const Graph &g, int s){ int n = g.size(); Edges es; Weight res = 0; vector<bool> visited(n); priority_queue<Edge> Q; Q.push(Edge(-1, s, 0)); while(!Q.empty()){ Edge e = Q.top(); Q.pop(); if(visited[e.to]) continue; es.push_back(e); res += e.weight; visited[e.to] = true; EACH(i, g[e.to]) if(!visited[i->to]) Q.push(*i); } return make_pair(res, es); } int N; int main(){ while(~scanf("%d", &N)){ Graph g(N); for(int i = 0; i < N; ++i)for(int j = 0; j < N; ++j){ int v; scanf("%d", &v); g[i].push_back(Edge(i, j, v)); } EACH(i, g){ EACH(j, *i){ } } printf("%d\n", prim(g, 0).first); } return 0; }