题目链接：HDU6005-Pandaland

题意：

n个点，m条无向边，问最小环。

题解：

考虑数据范围，我们可以枚举边，然后对于这条边，我们考虑这两点间除去这条边的最短路，最短路加上该边的长度即为过当前这条边的最小环。注意，需要加一个优化，跑最短路的时候，若更新到一条边时，该边的边权大于之前所求得的最小环，直接continue。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 8e3 + 10;
const int MAXM = 4e3 + 10;
const int inf = 0x3f3f3f3f;
int T, m;
struct EDGE
{
    int u, v, w, nxt;
} edge[MAXM << 1];
int ecnt = 0, fir[MAXN];
int ans;
void addedge(int u, int v, int w)
{
    edge[ecnt].u = u, edge[ecnt].v = v, edge[ecnt].w = w, edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
    swap(u, v);
    edge[ecnt].u = u, edge[ecnt].v = v, edge[ecnt].w = w, edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
ll getid(ll xx, ll yy)
{
    xx += 1e5 + 10;
    yy += 1e5 + 10;
    return xx * 100000ll + yy;
}
unordered_map<ll, int> mp;
bool used[MAXN];
int dis[MAXN];
void dijkstra(int st, int ed)
{
    priority_queue<pair<int, int>> que;
    while (!que.empty())
        que.pop();
    memset(dis, 0x3f, sizeof(dis));
    memset(used, 0, sizeof(used));
    dis[st] = 0;
    que.push({-dis[st], st});
    while (!que.empty())
    {
        int u = que.top().second;
        que.pop();
        if (used[u])
            continue;
        used[u] = 1;
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (w >= ans)
                continue;
            if ((u == st && v == ed) || (u == ed && v == st))
                continue;
            if (used[v])
                continue;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                que.push({-dis[v], v});
            }
        }
    }
}
int main()
{
    scanf("%d", &T);
    int icase = 0;
    while (T--)
    {
        ecnt = 0;
        memset(fir, -1, sizeof(fir));
        scanf("%d", &m);
        int cnt = 0;
        mp.clear();
        for (int i = 1; i <= m; i++)
        {
            int x1, y1, x2, y2, w;
            scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &w);
            if (!mp.count(getid(x1, y1)))
                mp[getid(x1, y1)] = ++cnt;
            if (!mp.count(getid(x2, y2)))
                mp[getid(x2, y2)] = ++cnt;
            addedge(mp[getid(x1, y1)], mp[getid(x2, y2)], w);
        }
        ans = inf;
        for (int i = 0; i < m; i++)
        {
            int id = i * 2;
            int u = edge[id].u, v = edge[id].v;
            dijkstra(u, v);
            if (dis[v] == inf)
                continue;
            ans = min(ans, dis[v] + edge[id].w);
        }
        if (ans == inf)
            printf("Case #%d: 0\n", ++icase);
        else
            printf("Case #%d: %d\n", ++icase, ans);
    }
    return 0;
}