题目：

首先，对于和 1 相连的点，一定是从某个点出发，回到另一个点；

所以需要枚举起点和终点，但做 n 遍 dijkstra 不太可行；

可以进行多起点最短路，一次知道了以一些点作为起点、另一些点作为终点的答案；

于是问题是如何划分起点和终点，使一定能找到最优解；

二进制划分，枚举每一位，这一位是 0/1 分成两部分，那么任意不同的两个数一定某一次被分到了不同的集合；

具体做法可以是从 1 出发，不让起点回到 1，不让终点来到 1，最后看看终点的 dis；

也可以干脆去掉 1，起点的 dis 值是从 1 到它的距离；

注意分成两部分后要分别跑一遍是起点和终点的。

代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int const maxn=5005,maxm=20005,inf=0x3f3f3f3f;int n,m,hd[maxn],ct,to[maxm],nxt[maxm],w[maxm],dis[maxn],mx,ans=inf;int son[maxn],ss,wt[maxn],wc[maxn];bool vis[maxn],st[maxn],ed[maxn];priority_queue
          
           
             >q;void add(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; w[ct]=z; hd[x]=ct;}void dijkstra(){ while(q.size())q.pop(); memset(vis,0,sizeof vis); memset(dis,0x3f,sizeof dis); dis[1]=0; q.push(make_pair(0,1));// for(int i=1,x;i<=ss;i++)// if(st[x=son[i]])dis[x]=wt[x],q.push(make_pair(-dis[x],x));// vis[1]=1; while(q.size()) { int x=q.top().second; q.pop(); if(vis[x])continue; vis[x]=1; for(int i=hd[x],u;i;i=nxt[i]) { if(vis[u=to[i]]||st[x]&&u==1||x==1&&ed[u])continue;// if(vis[u=to[i]])continue; if(dis[u]>dis[x]+w[i]) dis[u]=dis[x]+w[i],q.push(make_pair(-dis[u],u)); } } for(int i=1,x;i<=ss;i++) if(ed[x=son[i]])ans=min(ans,dis[x]+wc[x]);}int main(){ scanf("%d%d",&n,&m); int tmp=n; while(tmp)mx++,tmp/=2; for(int i=1,x,y,a,b;i<=m;i++) { scanf("%d%d%d%d",&x,&y,&a,&b); add(x,y,a); add(y,x,b); if(x==1)son[++ss]=y,wt[y]=a,wc[y]=b; if(y==1)son[++ss]=x,wt[x]=b,wc[x]=a; } for(int i=0;i