题目大意：$n$ 个点，$m$ 条边的无向图，边权只有两种，小的为 $a$，大的为 $b$。

对于每个点 $p$，询问在这张图所有的最小生成树上，$1$ 到 $p$ 的最短距离的最小值。

$2\le n\le 70,1\le m\le 200,1\le a<b\le 10^7$。

---

妙啊，真的太妙了。

有以下几个结论：（以下称边权为 $a$ 的叫轻边，边权为 $b$ 的叫重边）

结论 1：如果原图两个点中存在一条路径只有轻边，那么这两点在所有的最小生成树的路径上都不会有重边。根据最小生成树的性质，显然正确。

结论 2：如果把原图中所有重边删掉，会剩下一些联通块。一条路径可能在最小生成树上，当且仅当它没有离开一个联通块后再回到原来那个联通块中。根据结论 1 这也是对的。（注意，如果两个点属于一个联通块，但是这两个点有重边相连，那这个重边也是不能走的）

那么可以设计状态 $f[S][u]$，$S$ 是已经离开过的联通块集合，$u$ 是目前所在的点。

由于 $f[S][u]$ 可以转移到 $f[S][v]$ 时，$f[S][v]$ 也可以转移到 $f[S][u]$，所以要用最短路的方式更新。

时间复杂度 $O(2^nm\log(2^nm))$。其实由于边权只有两种，可以开两个队列，一个点最多被更新两次，复杂度是 $O(2^nm)$。

然而还有另一个结论：

结论 3：如果一个联通块大小 $\le 3$，那么在 $S$ 中不需要考虑这个联通块。证明，由于离开再回到一个联通块至少要两条重边（除了上面提到的直接一条重边相连，这个可以判掉），而当联通块大小 $\le 3$ 时内部可以通过不超过两条轻边互达。所以即使不记录，最优策略也不会离开再回到这个联通块。

那么只用记录大小 $\ge 4$ 的联通块即可。时间复杂度 $O(2^{n/4}m)$。

细节有点多。

#include
      
       using namespace std;#define FOR(i,a,b) for(int i=(a);i<=(b);i++)#define ROF(i,a,b) for(int i=(a);i>=(b);i--)#define MEM(x,v) memset(x,v,sizeof(x))inline int read(){    char ch=getchar();int x=0,f=0;    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();    return f?-x:x;}int n,m,a,b,w[77][77],id[18],cnt,tmp,f[20000000],q1[20000000],q2[20000000],h1,r1,h2,r2;bool vis1[77],vis2[77];int dfs1(int u){    vis1[u]=true;    int s=1;    FOR(i,1,n) if(w[u][i]==a && !vis1[i]) s+=dfs1(i);    return s;}void dfs2(int u,int c){    vis2[u]=true;    id[u]=c;    FOR(i,1,n) if(w[u][i]==a && !vis2[i]) dfs2(i,c);}inline int at(int x,int y){
    return x*n+y-1;}int main(){    n=read();m=read();a=read();b=read();    FOR(i,1,m){        int u=read(),v=read();        w[u][v]=w[v][u]=read();    }    FOR(i,1,n) if(!vis1[i]) if(dfs1(i)>=4) dfs2(i,++cnt);    tmp=cnt;    MEM(vis1,0);    FOR(i,1,n) if(!vis1[i]) if(dfs1(i)<4) dfs2(i,++cnt);    MEM(f,0x7f);    f[at(0,1)]=0;    q1[h1=r1=1]=at(0,1);q2[h2=r2=1]=at(0,1);    while(h1<=r1 || h2<=r2){        int u;        if(h1>r1) u=q2[h2++];        else if(h2>r2) u=q1[h1++];        else if(f[q1[h1]]
       
        f[u]+w[y][i]){                f[v]=f[u]+w[y][i];                if(w[y][i]==a) q1[++r1]=v;                else q2[++r2]=v;            }        }    }    FOR(i,1,n){        int ans=2e9;        FOR(j,0,(1<