题目：
按二进制每一位是 0/1 把 1 号点的儿子分成两组，分别作为起点和终点跑多起点最短路，最优解的起点和终点总有一次会被分到不同组里；
太久没写 dijkstra 竟然WA了4次...别忘了 priority_queue 是大根堆-_-，还要注意循环计数的 i，j 不要重了...
代码如下：
#include#include #include #include #include using namespace std;int const xn=40005,xm=1e5+5,inf=0x3f3f3f3f;int n,m,hd[xn],ct,nxt[xm<<1],to[xm<<1],w[xm<<1],dis[xn],ans;bool vis[xn],in[xn],out[xn];struct N{ int d,id; bool operator < (const N &y) const { return d>y.d;}//>};priority_queue q;int rd(){ int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return f?ret:-ret;}void add(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; w[ct]=z; hd[x]=ct;}void dij(){ memset(vis,0,sizeof vis); while(q.size()) { int x=q.top().id; q.pop(); if(vis[x])continue; vis[x]=1; for(int i=hd[x],u;i;i=nxt[i]) { if(vis[u=to[i]]||(u==1&&out[x])||(x==1&&in[u]))continue; if(dis[u]>dis[x]+w[i]) dis[u]=dis[x]+w[i],q.push((N){dis[u],u}); } } ans=min(ans,dis[1]);}int main(){ n=rd(); m=rd(); for(int i=1,x,y,z,k;i<=m;i++) { x=rd(); y=rd(); z=rd(); k=rd(); add(x,y,z); add(y,x,k); } int cnt=0,t=n; while(t)cnt++,t/=2; ans=inf; for(int i=0;i