畅通工程.txt

来自「浙江大学研究生复试上机题目及解答。欢迎大家下载。」· 文本 代码 · 共 52 行

//test
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int MMAX = 110;
int path[MMAX][MMAX];
int n,m;
typedef pair<int,int> node;
int prime() {
    priority_queue<node> pq;
    int i,j,cost = 0;
    bool vis[MMAX] = {0};
    for (i=2;i<=m;i++) {
        if (path[1][i] != -1) {
            pq.push(node(-path[1][i],i));
        }
    }
    vis[1] = true;
    while (!pq.empty()) {
        node now = pq.top();
        pq.pop();
        if (vis[now.second]) continue;
        cost += -now.first;
        vis[now.second] = true;
        for (i=1;i<=m;i++) {
            if (!vis[i] && path[now.second][i] != -1) {
                pq.push(node(-path[now.second][i],i));
            }
        }
    }    
    for (i=1;i<=m;i++) {
        if (!vis[i]) return -1;
    }
    return cost;
}
int main() {
    int i,j;
    while (scanf("%d %d",&n,&m),n) {
        memset(path,-1,sizeof(path));
        for (i=0;i<n;i++) {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            path[a][b] = (path[a][b]==-1) ? c : min(c,path[a][b]);
        }
        if ((i=prime()) != -1) printf("%d\n",i);
        else puts("?");
    }
}