题意：给你点和边，让你找最小环的权值，其权值是所有边权的和，没环输出-1。
解法：枚举每一条边，找到其端点，做最短路。、
#include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> using namespace std; const int N=8e3+55; const int INF=0x3f3f3f3f; int head[N],tot,dis[N],ans; pair<int,int>aa,bb; map<pair<int,int>,int>mp; bool vis[N]; struct node { int u,to,next,w; } e[N*N]; void add(int u,int v,int w) { e[tot].u=u; e[tot].to=v; e[tot].next=head[u]; e[tot].w=w; head[u]=tot++; } struct ct { int w,id; bool operator < (const ct &A)const { return w>A.w; } }; int dij(int s,int t,int ban) { memset(dis,INF,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue<ct>Q; dis[s]=0; ct q,p; q.w=0,q.id=s; Q.push(q); while(!Q.empty()) { q=Q.top(); Q.pop(); int u=q.id; if(q.w>=ans) return -1; if(vis[u]) continue; if(u==t) return q.w; vis[u]=1; for(int i=head[u]; ~i; i=e[i].next) { if(i==ban||(i^1)==ban) continue; int v=e[i].to; if(dis[v]>dis[u]+e[i].w) { dis[v]=dis[u]+e[i].w; p.w=dis[v],p.id=v; Q.push(p); } } } return -1; } int main() { int T,tas=1; for(scanf("%d",&T); T--;) { int n,x,now=0; memset(head,-1,sizeof(head)); tot=0; scanf("%d",&n); mp.clear(); for(int i=1; i<=n; ++i) { scanf("%d%d%d%d%d",&aa.first,&aa.second,&bb.first,&bb.second,&x); if(!mp[aa]) mp[aa]=++now; if(!mp[bb]) mp[bb]=++now; add(mp[aa],mp[bb],x); add(mp[bb],mp[aa],x); } ans=999999999; for(int i=0; i<tot; i+=2) { int w,u=e[i].u,v=e[i].to; w=dij(u,v,i); if(w!=-1) ans=min(ans,w+e[i].w); } if(ans==999999999) ans=0; printf("Case #%d: %d ",tas++,ans); } }