传送门：https://www.luogu.org/problem/U91354
这道题考场上打了一个dijkstra的暴力，出题人只给了50分。（tip—看dijkstra的性质，第一个访问到的地下党就是最近的，so，直接跳出）
可以看出上面的暴力要跑 k遍dijkstra 复杂度巨大
想想怎么优化呢？
我们可以看一个int的32位二进制的数，当第i位为0或1，那么这两个数一定不相等。
所以我们可以根据这一点，每次枚举int的第几位，建一个超级源点与那些第i位为1的党员连一条0的边，再建一个超级汇点与那些第i位为0的党员连一条0的边。（实际代码书写，看你想怎么写，可以不真的建出来也可以建出来）
那么我们就只需要跑32遍dijkstra就可以。实测会T，那么怎么办？
你可以把那些党员离散化一下，那么你需要枚举的最高的位数就会变小些。（真正实现你可以真的离散化，也可以不用离散化排个序即可）
我同学的代码（建出了图，离散化）：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define INF 0x3f3f3f3f #define N 1000010 using namespace std; priority_queue<pair<int,int> >q; int T,n,m,k,Head[N],ver[N*2],nex[N*2],edge[N*2],tot,a[N],b[N],num[N][31],maxn,ss,tt,st,ans,d[N]; int last[N]; bool v[N]; inline int read(){ char c=getchar();int x=0; while(c<'0' || c>'9') c=getchar(); while(c>='0' && c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar(); return x; } void add(int x,int y,int z){ ver[++tot]=y;edge[tot]=z;nex[tot]=Head[x];Head[x]=tot; } void dijkstra(){ memset(d,0x3f,sizeof(d));memset(v,0,sizeof(v)); d[ss]=0;q.push(make_pair(0,ss)); while(q.size()){ int x=q.top().second;q.pop();if(v[x]) continue;v[x]=1; for(int i=Head[x];i;i=nex[i]){ int y=ver[i],z=edge[i]; //cout<<x<<" "<<y<<" fuck"<<endl; if(d[y]>d[x]+z){ d[y]=d[x]+z;q.push(make_pair(-d[y],y)); } } } } void clear(){ memset(Head,0,sizeof(Head));memset(ver,0,sizeof(ver)); memset(nex,0,sizeof(nex));memset(edge,0,sizeof(edge));tot=maxn=0; } int main(){ // freopen("underground.in","r",stdin); // freopen("underground.out","w",stdout); T=read(); while(T--){ n=read();m=read();k=read();clear();ss=0;tt=n+1;ans=INF; for(int i=1;i<=m;i++){ int u,v,z;u=read(),v=read(),z=read(),add(u,v,z),add(v,u,z); } st=tot; for(int i=1;i<=k;i++) a[i]=read(),last[a[i]]=Head[a[i]]; sort(a+1,a+k+1);int cnt=unique(a+1,a+k+1)-a-1; for(int i=1;i<=k;i++) b[i]=lower_bound(a+1,a+cnt+1,a[i])-a; for(int i=1;i<=k;i++){ int t=b[i],tmp=0; while(t){ num[i][++tmp]=t%2; t/=2;if(t==1){num[i][++tmp]=1;maxn=max(maxn,tmp);break;} } } for(int i=1;i<=maxn;i++){ for(int j=1;j<=k;j++){ if(num[j][i]) add(a[j],tt,0); else add(ss,a[j],0); } dijkstra();ans=min(ans,d[tt]); tot=st;for(int j=1;j<=k;j++) Head[a[j]]=last[a[j]];Head[ss]=Head[tt]=0; } if(ans==INF) printf("-1 "); else printf("%d ",ans); } return 0; }
我的代码（没有建源汇点，只排了序）：(其实不排序也是可以的......你想想)
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> #define R register using namespace std; const int N=100000; priority_queue< pair<int,int> > q; int T,tot,head[N+5],ver[(N+5)<<2],nex[(N+5)<<2],cost[(N+5)<<2],n,m,k,p[N+5],d[N+5],ans,cnt,mx,b[N+5]; inline void add(int x,int y,int z){ ver[++tot]=y;cost[tot]=z;nex[tot]=head[x];head[x]=tot; } int main (){ scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&m,&k); tot=0; mx=0;cnt=0; ans=1e9; memset(head,0,sizeof(head)); memset(ver,0,sizeof(ver)); memset(nex,0,sizeof(nex)); memset(cost,0,sizeof(cost)); for(R int x,y,z,i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } for(R int i=1;i<=k;i++) scanf("%d",&p[i]); sort(p+1,p+1+k); int lala=k; while(lala){ cnt++; lala>>=1; } for(R int i=1;i<=cnt;i++){ memset(d,0x3f,sizeof(d)); for(R int j=1;j<=k;j++){ if((j>>(i-1))&1){ d[p[j]]=0; q.push( make_pair(-d[p[j]],p[j])); } } while(q.size()){ int x=q.top().second;q.pop(); for(R int j=head[x];j;j=nex[j]){ if(d[ver[j]]>d[x]+cost[j]){ d[ver[j]]=d[x]+cost[j]; q.push( make_pair(-d[ver[j]],ver[j])); } } } for(R int j=1;j<=k;j++){ if(!((j>>(i-1))&1)) ans=min(ans,d[p[j]]); } } printf("%d ",ans==1e9? -1:ans); } return 0; }