#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector> 
#include <queue>
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
// int cost[MAXN][MAXN];
// int minCost[MAXN];
struct Edge {
	int to,cost;
};
vector<Edge> edge[MAXN];
typedef pair<int, int> Dot;
bool used[MAXN];
int costMin[MAXN];
int N; 

int prime()
{
	int ret = 0;
	priority_queue<Dot, vector<Dot>, greater<Dot> > que;
	memset(costMin, INF, sizeof(costMin));
	memset(used, false, sizeof(used));
	costMin[0] = 0;
	//used[0] = true;
	que.push(Dot(0, 0));
	for (int i = 0; i < N; i++) {
		Dot dot = que.top();
		while(used[dot.second]) {
			que.pop();
			dot = que.top();
		}
		que.pop();
		int v = dot.second;
		used[v] = true;
		ret += dot.first;
		Edge es;
		for (int j = 0; j < edge[v].size(); j++) {
			es = edge[v][j];
			if (costMin[es.to] > es.cost) {
				costMin[es.to] = es.cost;
				que.push(Dot(costMin[es.to], es.to));
			}
		}
	}
	return ret;
}

int main()
{
	while(~scanf("%d", &N))
	{
		for (int i = 0; i < N; i++) {
			edge[i].clear();
		}
		Edge es;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				es.to = j;
				scanf("%d", &es.cost);
				edge[i].push_back(es);
			}
		}
		int d = prime();
		cout << d << endl;
	}
	return 0;
}

• Re:prime Ac 但是 prime+heap 总是wa,那位大神指点一下，感激不尽 (16) Timetraveller94 2018-01-27 11:56:38