【问题描述】 城市之间的公路交通可以用一个无向图表示。如下图所示： image.png 顶点表示城市、边表示城市之间有公路相连，边上的权值表示城市之间的公路长度。 编程解决以下问题： （1）输入城市信息和城市之间公路的信息，建立图的邻接矩阵存储结构 （2）为了使城市之间能够通信，将沿公路铺设光纤，给出合理的方案，使得光纤总耗费最小。 【输入形式】 第一行输入城市，城市之间用空格分开，输入q结束。 后面若干行，每行输入两座城市及城市间的公路长度，用空格分开。输入q结束。 输入起点城市名称。 【输出形式】起点城市出发得到的最小生成树，输出格式为(起点城市, 终点城市). 注：城市之间是英文逗号，并且没有空格。 【样例输入】 成都 西安 昆明 贵阳 武汉 株洲 q 成都 西安 842 成都 昆明 1100 成都 贵阳 967 西安 武汉 740 贵阳 武汉 1042 贵阳 株洲 607 武汉 株洲 409 q 成都 【样例输出】 (成都,西安) (西安,武汉) (武汉,株洲) (株洲,贵阳) (成都,昆明)

以下是Prim算法求解最小生成树的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
#define INF 0x3f3f3f3f

// 存储图的邻接矩阵
int graph[MAX][MAX];
// 存储城市名称
char cities[MAX][MAX];
// 存储城市数量
int n;

// Prim算法求最小生成树
void prim(int start) {
    int i, j, k;
    int min, sum = 0;
    int lowcost[MAX], closest[MAX], visited[MAX];

    // 初始化
    for (i = 0; i < n; i++) {
        lowcost[i] = graph[start][i];
        closest[i] = start;
        visited[i] = 0;
    }
    visited[start] = 1;

    // n-1次循环，每次加入一个新的顶点
    for (i = 1; i < n; i++) {
        min = INF;
        // 找到离当前生成树最近的顶点
        for (j = 0; j < n; j++) {
            if (!visited[j] && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        // 输出当前加入的边
        printf("(%s,%s)\n", cities[closest[k]], cities[k]);
        sum += min;
        visited[k] = 1;
        // 更新距离和最小的顶点
        for (j = 0; j < n; j++) {
            if (!visited[j] && graph[k][j] < lowcost[j]) {
                lowcost[j] = graph[k][j];
                closest[j] = k;
            }
        }
    }
    printf("总耗费：%d\n", sum);
}

int main() {
    int i, j, len;
    char city1[MAX], city2[MAX];
    int len1, len2, dist;

    // 输入城市名称
    n = 0;
    while (1) {
        scanf("%s", cities[n]);
        if (strcmp(cities[n], "q") == 0) break;
        n++;
    }

    // 初始化邻接矩阵
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            graph[i][j] = INF;
        }
    }

    // 输入城市之间的公路长度
    while (1) {
        scanf("%s", city1);
        if (strcmp(city1, "q") == 0) break;
        scanf("%s%d", city2, &dist);
        // 查找城市名称对应的下标
        for (i = 0; i < n; i++) {
            if (strcmp(cities[i], city1) == 0) {
                len1 = i;
            }
            if (strcmp(cities[i], city2) == 0) {
                len2 = i;
            }
        }
        // 更新邻接矩阵
        graph[len1][len2] = graph[len2][len1] = dist;
    }

    // 输入起点城市名称
    scanf("%s", city1);
    // 查找起点城市的下标
    for (i = 0; i < n; i++) {
        if (strcmp(cities[i], city1) == 0) {
            len = i;
            break;
        }
    }

    // 求解最小生成树
    prim(len);

    return 0;
}

该代码使用邻接矩阵存储图，其中`graph[i][j]`表示顶点i和j之间的距离。`cities`数组用来存储城市名称，`n`表示城市数量。`prim`函数是使用Prim算法求解最小生成树的函数，参数`start`表示起点。该函数使用了三个辅助数组：`lowcost`数组表示顶点到当前生成树的最小距离，`closest`数组表示距离当前生成树最近的顶点，`visited`数组表示顶点是否已经加入到生成树中。算法的核心部分是每次选择离当前生成树最近的顶点，并将该顶点加入到生成树中，同时更新与该顶点相邻的顶点的距离和最小值和最近的顶点。最终输出生成树的边和总耗费。