题目的意思：
一条路径的起点和终点相同，就是一只「环」。
有向图的环，可以特地称作「有向环」；无向图的环，可以特地称作「无向环」。环上每个点都恰好连着两条边。
无向环以另一种角度来看，就是两条路径，两条路径的起点相同、终点也相同。
习惯规定一个环至少三个点。
藉由Floyd-Warshall Algorithm 的过程，顺手穷举所有可能的最小环。代码如下：
#include <stdio.h> #include <string.h> int n;//交叉点的数量 int m;//路径的跳数 int edge[101][101];//记录每条边的情况,以及使用情况 int d[101][101];//记录顶点间距离 int path[101][101];//记录路径 int ans_path[101];//答案路径 int ans_len;//记录路径的长度 #define INFINITE 10000000 int min = INFINITE;//源到源的最小路径长度 //获得路径 void get_path(int i, int j) { ans_path[ans_len ++] = j; if (i == j) return; get_path(i, path[i][j]); } int main(void) { int i, j, k, source, destination, distance, flag1; //输入数据 while (1) { scanf("%d", &n); if (n == -1) break; scanf("%d", &m); //初始化edge for (i = 1; i <= n; i ++) { edge[i][i] = INFINITE; path[i][i] = INFINITE; for (j = i; j <= n; j ++) edge[i][j] = edge[j][i] = INFINITE; } for (i = 0; i < m; i ++) { scanf("%d%d%d", &source, &destination, &distance); if (edge[source][destination] > distance) { edge[source][destination] = edge[destination][source] = distance; path[source][destination] = source; path[destination][source] = destination; } } min = INFINITE; memcpy(d, edge, sizeof(edge)); for (k = 1; k <= n; k ++) { for (i =1; i < k; i ++) for (j = 1; j < k; j ++) if (i != j) { if ( edge[k][i] + d[i][j] + edge[j][k] < min) { min = edge[k][i] + d[i][j] + edge[j][k]; ans_len = 0; ans_path[ans_len ++] = k; get_path(i, j); } } for (i = 1; i <= n; i ++) { for (j = 1; j <=n; j ++) { if (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; path[i][j] = path[k][j]; } //printf("%d:%d ", d[i][j], path[i][j]); } // printf("\n"); } // printf("\n\n"); } if (min == INFINITE) printf("No solution.\n"); else { while (ans_len) printf("%d ", ans_path[-- ans_len]); printf("\n"); } } return 0; }