読者です 読者をやめる 読者になる 読者になる

PKU1258 Agri-Net

最小全域木のテンプレ問題
primで解きましたがpriority_queueは使いませんでしたw

//PKU1258
#include<iostream>
#include<cstdio>
#define INF 1000000
using namespace std;

int n;
bool used[100];
int cost[100][100];
int mincost[100];

int Prim(){
	for(int i = 0; i < n; i++){
		mincost[i] = INF;
		used[i] = false;
	}
	mincost[0] = 0;
	int res = 0;
	while(true){
		int v = -1;
		for(int u = 0; u < n; u++){
			if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
		}
		if(v == -1) break;
		used[v] = true; 
		res += mincost[v];

		for(int u = 0; u < n; u++){ 
		mincost[u] = min(mincost[u], cost[v][u]);
		}
	}
	return res;
}
int main(){
	while(scanf("%d", &n) != EOF){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				scanf("%d", &cost[i][j]);
			}
		}
		printf("%d\n", Prim());
	}
	return 0;
}