\(\bigstar\texttt{Hint}\)：发现没有什么好的突破口？为什么不想想怎样才能实现题目中 \(2^x\) 的加减法呢？
可见每次加减法，我们要做的是将添加的 \(1\) 和右边的连续的 \(1\) 合并为一整段，可以用线段树 \(\mathcal{O(\log n)}\) 实现。
怎样比较大小呢？考虑如何找到两个串第一个不同的位置，则我们需要的就是二分区间、比较这两段区间是否相同。用一个 Hash 即可。
然后就成为了屎题
#define Maxn 100005
#define Maxm 1800005
#define mod 1000000007
int n,m,s,t,tot,MAX,tp,All;
int uu[Maxn],vv[Maxn],dd[Maxn],Pow2[Maxm];
int hea[Maxn],nex[Maxn<<1],ver[Maxn<<1],edg[Maxn<<1];
int pre[Maxn],sta[Maxn];
bool vis[Maxn];
inline void add(int x,int y,int d)
{ ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=d; }
struct TREE
{
int Hash,ls,rs,rmost,laz; // pushdown !!!!
TREE(int H=0,int Ls=0,int Rs=0,int Rmost=-1,int Laz=-1):
Hash(H),ls(Ls),rs(Rs),rmost(Rmost),laz(Laz){}
inline void Push(int x,int nl,int nr)
{
if(x==0) Hash=0,rmost=nr,laz=x;
else Hash=(Pow2[nr-nl+1]-1+mod)%mod,rmost=-1,laz=x;
}
}tree[Maxm<<4];
inline void pushdown(int p,int nl,int nr)
{
if(tree[p].laz!=-1)
{
int mid=(nl+nr)>>1;
tree[p].ls=++All,tree[tree[p].ls].Push(tree[p].laz,nl,mid);
tree[p].rs=++All,tree[tree[p].rs].Push(tree[p].laz,mid+1,nr);
tree[p].laz=-1;
}
}
inline void pushup(int p,int nl,int nr)
{
int lson=tree[p].ls,rson=tree[p].rs,mid=(nl+nr)>>1;
tree[p].Hash=(1ll*tree[lson].Hash*Pow2[nr-mid]%mod+tree[rson].Hash)%mod;
tree[p].rmost=max(tree[lson].rmost,tree[rson].rmost);
}
bool Comp(int pl,int pr,int nl,int nr)
{
if(nl==nr) return tree[pl].Hash<tree[pr].Hash;
pushdown(pl,nl,nr),pushdown(pr,nl,nr);
int mid=(nl+nr)>>1;
if(tree[tree[pl].ls].Hash!=tree[tree[pr].ls].Hash)
return Comp(tree[pl].ls,tree[pr].ls,nl,mid);
else return Comp(tree[pl].rs,tree[pr].rs,mid+1,nr);
}
int Find(int p,int nl,int nr,int l,int r)
{
if(nl>=l && nr<=r) return tree[p].rmost;
pushdown(p,nl,nr);
int mid=(nl+nr)>>1,ret=-inf;
if(mid>=l) ret=max(ret,Find(tree[p].ls,nl,mid,l,r));
if(mid<r) ret=max(ret,Find(tree[p].rs,mid+1,nr,l,r));
return ret;
}
bool Check0(int p,int nl,int nr,int x)
{
if(nl==nr) return tree[p].Hash==0;
pushdown(p,nl,nr);
int mid=(nl+nr)>>1;
if(mid>=x) return Check0(tree[p].ls,nl,mid,x);
return Check0(tree[p].rs,mid+1,nr,x);
}
void change(int pl,int pr,int nl,int nr,int l,int r,int x)
{
if(nl>=l && nr<=r) { tree[pr].Push(x,nl,nr); return; }
pushdown(pl,nl,nr);
tree[pr]=tree[pl];
int mid=(nl+nr)>>1;
if(mid>=l)
tree[pr].ls=++All,tree[All]=tree[tree[pl].ls],
change(tree[pl].ls,tree[pr].ls,nl,mid,l,r,x);
if(mid<r)
tree[pr].rs=++All,tree[All]=tree[tree[pl].rs],
change(tree[pl].rs,tree[pr].rs,mid+1,nr,l,r,x);
pushup(pr,nl,nr);
}
struct NODE
{
int num,dist_rt;
NODE(int N=0,int D=0):num(N),dist_rt(D){}
bool friend operator < (NODE x,NODE y)
{ return Comp(y.dist_rt,x.dist_rt,1,MAX); }
int friend operator + (NODE p,int x)
{
int n2=++All;
if(Check0(p.dist_rt,1,MAX,x)) change(p.dist_rt,n2,1,MAX,x,x,1);
else
{
int pos=Find(p.dist_rt,1,MAX,1,x),n1=++All;
change(p.dist_rt,n1,1,MAX,pos+1,x,0);
change(n1,n2,1,MAX,pos,pos,1);
}
return n2;
}
}ds[Maxn];
inline void Short_path()
{
priority_queue<NODE> q;
ds[s]=NODE(s,1);
for(int i=1;i<=n;i++) if(i!=s) ds[i]=NODE(i,2);
q.emplace(s,0);
while(!q.empty())
{
NODE cur=q.top(); q.pop();
int Now=cur.num;
if(vis[Now]) continue;
vis[Now]=true;
for(int i=hea[Now];i;i=nex[i])
{
NODE tmp=NODE(ver[i],ds[Now]+edg[i]);
if(ds[ver[i]]<tmp)
ds[ver[i]]=tmp,pre[ver[i]]=Now,
q.push(ds[ver[i]]);
}
}
}
int main()
{
n=rd(),m=rd(),All=2;
for(int i=1;i<=m;i++) uu[i]=rd(),vv[i]=rd(),dd[i]=rd(),MAX=max(MAX,dd[i]);
MAX=MAX*log2(n)+1000;
for(int i=1;i<=m;i++)
add(uu[i],vv[i],MAX-dd[i]),add(vv[i],uu[i],MAX-dd[i]);
s=rd(),t=rd(),Pow2[0]=1;
for(int i=1;i<=MAX;i++) Pow2[i]=Pow2[i-1]*2%mod;
if(s==t) { printf("0\n1\n%d\n",s); return 0; }
memset(pre,-1,sizeof(pre));
tree[1].Push(0,1,MAX);
tree[2].Push(1,1,MAX);
Short_path();
if(pre[t]==-1) printf("-1\n");
else
{
sta[++tp]=t;
for(int x=pre[t];x!=-1;x=pre[x]) sta[++tp]=x;
printf("%d\n%d\n",tree[ds[t].dist_rt].Hash,tp);
for(int i=tp;i>=1;i--) printf("%d ",sta[i]);
printf("\n");
}
return 0;
}