HDU-1102-Constructing Roads

这题就是稠密图，所以我们就用Prim。
然后题中要求的是需要新建的路的最小值，所以已经建成的路，我们直接使用就可以了，把它设置为0，然后走这条路就是最短的。
这题还是多组输入输出，所以还是用while循环输入。

#include <cstdio>
int map[105][105];
int vis[105], d[105];
const int INF = 0x3f3f3f3f;
int n, q, ans, s, e;

void init()
{
    for (int i = 0; i < 105;i++) {
        vis[i] = 0;
        d[i] = INF;
    }
} 

void Prim()
{
    d[1] = 0;
    ans = 0;
    for (int i = 1; i <= n;i++) {
        int end = -1;
        for (int j = 1; j <= n;j++) {
            if (!vis[j]&&(end==-1||d[end]>d[j]))
                end = j;
        }
        vis[end] = 1;
        ans += d[end];
        for (int j = 1; j <= n;j++) {
            if (!vis[j]&&d[j]>map[end][j])
                d[j] = map[end][j];
        }
    }
}

int main()
{
    while (scanf("%d", &n)!=EOF) {
        for (int i = 1; i <= n;i++) {
            for (int j = 1; j <= n;j++) {
                scanf("%d", &map[i][j]);
            }
        }
        init();
        scanf("%d", &q);
        while (q--) {
            scanf("%d%d", &s, &e);
            map[s][e] = map[e][s] = 0;
        }
        Prim();
        printf("%d
", ans);
    }
    // getchar();
    // getchar();
    return 0;
}