题目大意：给定一张无向图，每条边从两个方向走各有一个权值，，求从点1往出走至少一步之后回到点1且不经过一条边多次的最短路 显然我们需要从点1出发走到某个和点1相邻的点上，然后沿最短路走到另一个和点1相邻的点上，然后回到点1 那么我们将与点1相邻的点都设为关键点，然后将点1从图中删除，题目转化成了给定图上的一些关键点求最近点对 枚举每个点显然会T 考虑每次将关键点划分为两个集合反转做一次 这样只要任意点对都被分别划分到两个集合中至少一次，那么答案就被更新完了 如何划分呢？我们考虑按照二进制拆分，对于每一位划分一次，将该位上为集合中 由于两个数至少有一位不同，因此任意点对至少被划分了一次 这样划分次就够了
;struct abcd{int to,f,next;}table[M<<2];int head[M],tot;int n,m,top,ans=0x3f3f3f3f;pair<int,pair<int,int> >stack[M<<1];int f[M];void Add(int x,int y,int z){table[++tot].to=y;table[tot].f=z;table[tot].next=head[x];head[x]=tot;}namespace Heap{int heap[M],pos[M],top;void Push_Up(int t){while(t>1){if( f[heap[t]]<f[heap[t>>1]] )swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t>>=1;elsebreak;}}void Insert(int x){heap[++top]=x;pos[x]=top;Push_Up(top);}void Pop(){pos[heap[1]]=0;heap[1]=heap[top–];if(top) pos[heap[1]]=1;int t=2;while(t<=top){if( f[heap[t+1]]<f[heap[t]] )++t;if( f[heap[t]]<f[heap[t>>1]] )swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t<<=1;elsebreak;}}}void Dijkstra(){using namespace Heap;int i;for(i=1;i<=n;i++)Insert(i);while(Heap::top){int x=heap[1];Pop();for(i=head[x];i;i=table[i].next)if(f[table[i].to]>f[x]+table[i].f){f[table[i].to]=f[x]+table[i].f;Push_Up(pos[table[i].to]);}}}int main(){int i,j,x,y,z1,z2;cin>>n>>m;for(i=1;i<=m;i++){scanf(“%d%d%d%d”,&x,&y,&z1,&z2);if(x>y) swap(x,y),swap(z1,z2);if(x==1)stack[++top]=make_pair(y,make_pair(z1,z2));elseAdd(x,y,z1),Add(y,x,z2);}for(j=1;j<=n;j<<=1){memset(f,0x3f,sizeof f);for(i=1;i<=top;i++)if(i&j)f[stack[i].first]=stack[i].second.first;Dijkstra();for(i=1;i<=top;i++)if(~i&j)ans=min(ans,f[stack[i].first]+stack[i].second.second);memset(f,0x3f,sizeof f);for(i=1;i<=top;i++)if(~i&j)f[stack[i].first]=stack[i].second.first;Dijkstra();for(i=1;i<=top;i++)if(i&j)ans=min(ans,f[stack[i].first]+stack[i].second.second);}cout<<ans<<endl;return 0;}
有希望在的地方，痛苦也成欢乐
