昨天晚上从Yasola那里偷来的一道题……
为什么Yasola这么优秀啊！！！！！
求求你别学了，我已经完全跟不上了……
因为看着题目并不是很难我也就写了一蛤，然后自以为是无脑题就疯狂WA……
emmmm…… 其实仔细想想还是挺简单的。
题意：
给你一张无向图，要你找出最小环。
点数 ( n \leq 100 )
思路：
对 floyd 进行简单增加一点代码。
floyd 算法剖解开来就是不断找到一个中间结点使得路径更短。而我们可以在这个中间结点加入最短路之前，将其固定为环上的一个点，这点必定不会被所有最短路夹在中间。
有一个非常显然的问题就是，当我固定一个中间结点的时候，我无法保证我所用的最短路为全局最短路。这个问题显著存在于floyd初期。
比如说
存在一个 ABCA 的环与一个 BCDB，其中 ( BD + DC < BC , AB + AC < BC )，而当我使 A 为固定结点，而我的 D 还不曾成为固定结点，也就不会被加入 BC 的最短路。
然而实际上并不要担心，这个环仍然会在floyd后期进行更新，因为对一个环来说，总存在最后一个被作为固定结点。
假设最糟糕的情况，D 结点是 ABCD 结点中最后一个被作为固定结点，那么不也能成功加入 BAC这条最短路径么。
AC Code
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))
using namespace std;
const int inf = 1e8;
const int maxn = 105;
int G[maxn][maxn];
int dis[maxn][maxn];
int main()
{
int n, m, u, v, w;
while (scanf("%d %d", &n, &m) != EOF) {
range(i, 1, n) range(j, 1, n) G[i][j] = i == j ? 0 : inf;
while (m--) {
scanf("%d %d %d", &u, &v, &w);
G[u][v] = G[v][u] = min(G[u][v], w);
}
range(i, 1, n) range(j, 1, n) dis[i][j] = G[i][j];
int ans = inf;
range(k, 1, n)
{
range(i, 1, k - 1) range(j, i + 1, k - 1) ans = min(ans, dis[i][j] + G[i][k] + G[k][j]);
range(i, 1, n) range(j, 1, n) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
ans == inf ? printf("It's impossible.\n") : printf("%d\n", ans);
}
return 0;
}