Constructing Roads POJ - 2421

题目链接：https://vjudge.net/problem/POJ-2421

思路：一些村庄，建一些路，使得所有村庄能相连，而且使得所有路长度之和最短。

题目说了，有些村庄之间已经建了路，说明有些路我们不需要建，那么在预处理的时候

把那些已经建过边的两个村庄的距离赋值为0，那么在跑最小生成树板子的时候就完成了

一些路已经建立的情况。

 #include <stdio.h>

 #include <iostream>

 #include <queue>

 using namespace std;

 const int inf = (int)1e9;

 const int N = ;

 int g[N][N];

 int dis[N];

 bool vis[N];

 int n;

 struct node{

     int loc;

     int v;

     bool friend operator<(const node& a,const node& b){

         return a.v > b.v;

     }

 };

 priority_queue<node > que;

 int prime(){

     que.push(node{,});

     dis[] = ;

     while(!que.empty()){

         int u = que.top().loc;

         que.pop();

         vis[u] = true;

         for(int v = ; v <= n; v++){

             if(!vis[v] && dis[v] > g[u][v]){

                 dis[v] = g[u][v];

                 que.push(node{v,dis[v]});

             }

         }

     }

     int ans = ;

     for(int i = ; i <= n; i++){

     //    printf("%d ",dis[i]);

         ans += dis[i];

     }

    // printf("\n");

     return ans;

 }

 int main(){

     scanf("%d",&n);

     for(int i = ; i <= n; i++)

         for(int j = ; j <= n; j++)

             scanf("%d",&g[i][j]);

     for(int i = ; i <= n; i++)

         dis[i] = inf;

     int m;

     scanf("%d",&m);

     int u,v;

     for(int i = ; i <= m; i++){

         scanf("%d%d",&u,&v);

         g[u][v] = g[v][u] = ;//已经有路的村庄

     }

     printf("%d\n",prime());

     return ;

 }