题解 | #继续畅通工程#

#include "bits/stdc++.h"

using namespace std;



class Graph{
public:
    int nodes;
    vector<list<pair<int,int>>> graph;


    Graph(int n,vector<pair<pair<int,int>,int>> edges) {
        nodes=n;
        graph=vector<list<pair<int,int>>>(n+1,list<pair<int,int>>());
        for (pair<pair<int,int>,int> edge: edges) {
            pair<int,int> no_value_edge=edge.first;
            int value=edge.second;
            pair<int,int> addEdge1(no_value_edge.first,value);
            pair<int,int> addEdge2(no_value_edge.second,value);
            graph[no_value_edge.first].push_back(addEdge2);
            graph[no_value_edge.second].push_back(addEdge1);
        }
    }

};

int primeGraph(Graph g,int start)
{
    int size = g.nodes;
    int cost[size+1];
    int visited[size+1];
    memset(cost, INT_MAX, (size+1) * sizeof(int));
    memset(visited, 0, (size+1) * sizeof(int));
    cost[start]=0;
    visited[start]=1;
    
    for (pair<int,int> edge: g.graph[start]) {
        cost[edge.first]=edge.second;
    }
    int sumCost=0;
    for (int i = 0; i <size-1; ++i) {
        int minCostIndex=0;
        int minCost=INT_MAX;
        for (int j = 1; j <= size; ++j) {
            if (!visited[j] && cost[j]<minCost)
            {
                minCost=cost[j];
                minCostIndex=j;
            }
        }

        visited[minCostIndex]=1;
        for (pair<int,int> edge: g.graph[minCostIndex]) {
            if (!visited[edge.first])
            {
                cost[edge.first]= min(edge.second,cost[edge.first]);
            }
        }
        sumCost+=minCost;
    }

    return sumCost;
}

int main(){
    int n;
    while (cin>>n)
    {
        if (!n)
            break;
        vector<pair<pair<int,int>,int>> edges(n*(n-1)/2);

        for (int i = 0; i < edges.size(); ++i) {
            int v1,v2,value;
            int isBuild;
            cin>>v1>>v2>>value>>isBuild;
            if (isBuild)
                value=0;
            pair<pair<int,int>,int> edge(pair<int,int>(v1,v2),value);
            edges[i]=edge;
        }
        Graph gra(n,edges);
        cout<<primeGraph(gra,1)<<endl;

    }
    return 0;
}

使用Prime算法构造最小生成树，值得注意的是对于已经建立好的道路则视为cost为0