怎么说呢
这题就是个模板题
但是
hud你妹夫啊说好的只有一组数据呢???
嗯???
wa到家都不认识了好吗
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std; typedef pair<int, int> pii;
struct cmp{
bool operator() (const pii a, const pii b){
return a.first > b.first;
}
}; int n, q, val[][], dist[];
bool vis[]; int prim(int s)
{
priority_queue<pii, vector<pii>, cmp> q;
memset(vis, false, sizeof vis);
for(int i = ; i <= n; i++){
dist[i] = val[s][i];
q.push(make_pair(dist[i], i));
}
vis[s] = true;
int res = ;
while(!q.empty()){
pii u = q.top();
q.pop();
if(vis[u.second]) continue;
vis[u.second] = true;
res += u.first;
for(int i = ; i <= n; i++){
if(!vis[i] && i != u.second && val[u.second][i] < dist[i]){
dist[i] = val[u.second][i];
q.push(make_pair(dist[i], i));
}
}
}
return res;
} int main()
{
while(~scanf("%d", &n)){
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++){
scanf("%d", &val[i][j]);
}
}
scanf("%d", &q);
while(q--){
int u, v;
scanf("%d%d", &u, &v);
val[u][v] = val[v][u] = ;
}
printf("%d\n", prim());
}
return ;
}