设G=(V,E)是一个带权图。图中的各边的费用（权）为正数。图中的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题是指在图G中找出费用最小的周游路线。如果找不到可行方案，则输出-1。 C语言实现，样例输入 4 1 2 30 1 3 6 1 4 4 2 3 5 2 4 10 3 4 20 样例输出 Copy 25 1 3 2 4 1

以下是C语言实现，使用了Dijkstra算法来求解最小周游路线：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 1000

typedef struct {
    int vertex;
    int weight;
} Edge;

int num_vertices, num_edges;
Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];
int adj_matrix[MAX_VERTICES][MAX_VERTICES];

int dijkstra(int start_vertex) {
    int visited[MAX_VERTICES] = {0};
    int dist[MAX_VERTICES];
    int prev[MAX_VERTICES];
    int i, j, u, min_dist;

    for (i = 0; i < num_vertices; i++) {
        dist[i] = INT_MAX;
        prev[i] = -1;
    }
    dist[start_vertex] = 0;

    for (i = 0; i < num_vertices - 1; i++) {
        min_dist = INT_MAX;
        for (j = 0; j < num_vertices; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        visited[u] = 1;
        for (j = 0; j < num_vertices; j++) {
            if (!visited[j] && adj_matrix[u][j] != -1) {
                if (dist[u] + adj_matrix[u][j] < dist[j]) {
                    dist[j] = dist[u] + adj_matrix[u][j];
                    prev[j] = u;
                }
            }
        }
    }

    min_dist = 0;
    for (i = 0; i < num_vertices; i++) {
        if (dist[i] == INT_MAX) {
            return -1;
        }
        min_dist += dist[i];
    }

    return min_dist;
}

int compare_edges(const void *a, const void *b) {
    Edge *edge_a = (Edge *)a;
    Edge *edge_b = (Edge *)b;
    return edge_a->weight - edge_b->weight;
}

int find(int *parent, int vertex) {
    if (parent[vertex] == -1) {
        return vertex;
    }
    return find(parent, parent[vertex]);
}

void union_sets(int *parent, int x, int y) {
    int x_root = find(parent, x);
    int y_root = find(parent, y);
    parent[x_root] = y_root;
}

int kruskal() {
    Edge result[MAX_VERTICES];
    int parent[MAX_VERTICES];
    int i, j, count;

    qsort(edges, num_edges, sizeof(Edge), compare_edges);

    for (i = 0; i < num_vertices; i++) {
        parent[i] = -1;
    }

    count = 0;
    for (i = 0; i < num_edges; i++) {
        Edge edge = edges[i];
        int x = find(parent, edge.vertex);
        int y = find(parent, (edge.vertex + 1) % num_vertices);
        if (x != y) {
            result[count++] = edge;
            union_sets(parent, x, y);
        }
    }

    if (count != num_vertices) {
        return -1;
    }

    int min_dist = 0;
    for (i = 0; i < count; i++) {
        min_dist += result[i].weight;
    }

    return min_dist;
}

int main() {
    int i, j;

    scanf("%d %d", &num_vertices, &num_edges);

    for (i = 0; i < num_vertices; i++) {
        for (j = 0; j < num_vertices; j++) {
            adj_matrix[i][j] = -1;
        }
    }

    for (i = 0; i < num_edges; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        u--;
        v--;
        edges[i].vertex = u;
        edges[i].weight = w;
        adj_matrix[u][v] = w;
        adj_matrix[v][u] = w;
    }

    int dist = dijkstra(0);
    if (dist == -1) {
        printf("-1\n");
        return 0;
    }

    int min_dist = kruskal();
    if (min_dist == -1 || min_dist > dist) {
        printf("-1\n");
    } else {
        printf("%d\n", min_dist);
        int parent[MAX_VERTICES];
        for (i = 0; i < num_vertices; i++) {
            parent[i] = -1;
        }
        for (i = 0; i < num_edges; i++) {
            int u = edges[i].vertex;
            int v = (edges[i].vertex + 1) % num_vertices;
            int x = find(parent, u);
            int y = find(parent, v);
            if (x != y) {
                printf("%d %d ", u + 1, v + 1);
                union_sets(parent, x, y);
            }
        }
        printf("%d\n", 1);
    }

    return 0;
}

这个实现包括了两种算法：Dijkstra算法和Kruskal算法。首先使用Dijkstra算法来求出任意两个点之间的最短路径。如果存在无法到达的点，则整个图不连通，直接输出-1。否则，使用Kruskal算法来求出最小生成树，并判断其是否为最小周游路线。如果最小生成树不是最小周游路线，则输出-1；否则，输出最小周游路线的长度和顶点的遍历顺序。