题有毒，题意是让你求一个最小权值的环。 思路：枚举每一条边然后每次跑一遍dij，再加上这条边的权值，就是结果了。 然后就TLE啦，那就剪枝，每次跑的时候如果遇到已经大于ans的结果是就直接break。
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <vector>
#define mod 1000000007
#define INF 0x3f3f3f3f
#define fuck() (cout << "----------------------------------------" << endl)
using namespace std;
const int maxn =
10000 +
5;
typedef pair<
int,
int> P;
map<P,int> num;
vector <P> vec[maxn];
int n,cnt,ans;
bool vis[maxn];
int dis[maxn];
struct EDGE
{
int u;
int v;
int w;
EDGE(){}
EDGE(
int a,
int b,
int c)
{
u = a , v = b, w = c;
}
};
EDGE edge[maxn];
void dij(
int source,
int end,
int cost)
{
for(
int i=
0; i<maxn; i++)
{
vis[i] =
false;
dis[i] = INF;
}
dis[source] =
0;
priority_queue<P,
vector<P>,greater<P> > q;
q.push(make_pair(
0,source));
while(!q.empty())
{
P p = q.top();
q.pop();
int u = p.second, d = p.first;
if(d + cost >= ans)
break;
if(vis[u])
continue;
vis[u] =
true;
for(
int i=
0; i<vec[u].size(); i++)
{
P temp = vec[u][i];
int v = temp.first;
int fck = temp.second;
EDGE e = edge[fck];
int c = e.w;
if(dis[v] > dis[u] + c)
{
dis[v] = dis[u] + c;
q.push(make_pair(dis[v],v));
}
}
}
ans = min(ans, dis[end] + cost);
}
int main()
{
int T, kases =
1;
scanf(
"%d",&T);
while(T--)
{
for(
int i=
0; i<maxn; i++)
vec[i].clear();
num.clear();
scanf(
"%d",&n);
cnt =
0;
for(
int i=
0; i<n; i++)
{
int x1,y1,x2,y2,w;
scanf(
"%d%d%d%d%d",&x1,&y1,&x2,&y2,&w);
P p1 = make_pair(x1,y1);
P p2 = make_pair(x2,y2);
if(!num.count(p1)) num[p1] = cnt++;
if(!num.count(p2)) num[p2] = cnt++;
int num1 = num[p1], num2 = num[p2];
vec[num1].push_back(make_pair(num2,i));
vec[num2].push_back(make_pair(num1,i));
edge[i] = EDGE(num1,num2,w);
}
ans = INF;
for(
int i=
0; i<n; i++)
{
int u = edge[i].u, v = edge[i].v, w = edge[i].w;
edge[i].w = INF;
dij(u,v,w);
edge[i].w = w;
}
if(ans == INF) ans =
0;
printf(
"Case #%d: %d\n",kases++,ans);
}
}
