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; }