题目链接: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;
}