用C语言解决该问题并给出完整代码【问题描述】 城市之间的公路交通可以用一个无向图表示。如下图所示： 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_CITY_NUM 100
#define INF 0x3f3f3f3f

int city_num = 0;
int graph[MAX_CITY_NUM][MAX_CITY_NUM];
char city_name[MAX_CITY_NUM][20];

int get_index(char* name) {
    for (int i = 0; i < city_num; i++) {
        if (strcmp(city_name[i], name) == 0) {
            return i;
        }
    }
    strcpy(city_name[city_num], name);
    return city_num++;
}

void build_graph() {
    for (int i = 0; i < MAX_CITY_NUM; i++) {
        for (int j = 0; j < MAX_CITY_NUM; j++) {
            graph[i][j] = INF;
        }
    }
    char city1[20], city2[20];
    int distance;
    while (1) {
        scanf("%s", city1);
        if (city1[0] == 'q') break;
        scanf("%s", city2);
        if (city2[0] == 'q') break;
        scanf("%d", &distance);
        int index1 = get_index(city1);
        int index2 = get_index(city2);
        graph[index1][index2] = graph[index2][index1] = distance;
    }
}

void prim(int start) {
    int dist[MAX_CITY_NUM];
    int visited[MAX_CITY_NUM];
    int parent[MAX_CITY_NUM];
    for (int i = 0; i < city_num; i++) {
        dist[i] = INF;
        visited[i] = 0;
        parent[i] = -1;
    }
    dist[start] = 0;
    visited[start] = 1;
    for (int i = 1; i < city_num; i++) {
        int min_dist = INF;
        int min_index = -1;
        for (int j = 0; j < city_num; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }
        if (min_index == -1) return;
        visited[min_index] = 1;
        for (int j = 0; j < city_num; j++) {
            if (!visited[j] && graph[min_index][j] < dist[j]) {
                dist[j] = graph[min_index][j];
                parent[j] = min_index;
            }
        }
    }
    for (int i = 0; i < city_num; i++) {
        if (i == start) continue;
        printf("(%s,%s) ", city_name[parent[i]], city_name[i]);
    }
}

int main() {
    build_graph();
    char start[20];
    scanf("%s", start);
    int start_index = get_index(start);
    prim(start_index);
    return 0;
}

注意事项：

1. 建立城市之间的邻接矩阵时，需要将所有边的权值初始化为一个较大的数（这里用INT_MAX）。
2. 输入城市名称时，需要判断是否为终止字符'q'，以此结束输入。
3. 在Prim算法中，需要记录每个顶点的最短距离、是否已访问、以及父节点等信息。