浙江大学机试 继续畅通工程 Easy *注意思想，极其重要

#include<iostream>
#include<vector>
#include<string>
using namespace std;

const int maxn = 1010;
const int INF = 10000000;

bool vis[maxn];
int dis[maxn];
int ma[maxn][maxn];
int n;

void init() {
    fill(ma[0], ma[0] + maxn * maxn, INF);
    fill(vis, vis + maxn, false);
    fill(dis, dis + maxn, INF);
}

int prim() {
    int ans = 0;
    dis[1] = 0;
    for (int u = 0; u < n; u++) {
        int index = -1;
        int Min = INF;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && Min > dis[i]) {
                index = i;
                Min = dis[i];
            }
        }
        if (index == -1)
            return -1;
        vis[index] = true;
        ans += dis[index];
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && ma[index][i] != INF && dis[i] > ma[index][i]) {
                dis[i] = ma[index][i];
            }
        }
    }
    return ans;
}

int main() {
    while (cin >> n) {
        int a, b, d, p;
        init();
        if (n == 0)
            break;
        for (int i = 0; i < n*(n - 1)/2; i++) {
            cin >> a >> b >> d >> p;
            if (p == 1)
                ma[a][b] = ma[b][a] = 0;
            else
                ma[a][b] = ma[b][a] = d;
        }
        cout << prim() << endl;
    }
    return 0;
}