题目也没有给出什么很特殊的性质，所以考虑能不能高精度最短路。
dijkstra 中涉及的运算主要是两个：加法和比较大小。
注意到题目给出的边权是 2 k 2^k 2k 的形式，我们不如直接用二进制表示每一个数。
而比较大小的实质是从高到低找到第一个不相等的位，这个我们可以用哈希+二分实现。
发现加法并不是两个大数相加，而是一个大数
x
x
x 加上一个
2
m
2^m
2m（代码中的具体体现是 dis[u]+w[i]），这样做的是实质是从
x
x
x 的第
m
m
m 位开始找到最长的一段
1
1
1，并把这一段
1
1
1 置为
0
0
0，把下一个
0
0
0 置为
1
1
1。也就是区间置零和单点修改。
容易联想到用线段树维护每一个数，而每次相加找最长的连续的 1 1 1 可以在线段树上二分，区间置零和单点修改只需要可持久化一下就好（加法在 dijkstra 最多只会进行 m m m 次）。同时第一个比较大小也可以变成在线段树上二分。
还有一个小细节就是我们先可以建一棵全零树，然后区间置零时直接连向全零树的对应区间就行。
代码如下：
#include<bits/stdc++.h>
#define LN 17
#define N 100050
#define mod 1000000007
#define lc(u) t[u].ch[0]
#define rc(u) t[u].ch[1]
using namespace std;
const unsigned int base=19260817;
int n,m,S,T;
int cnt,head[N],to[N<<1],w[N<<1],nxt[N<<1];
int node,rt0,rt1;
int pre[N],dis[N];
bool vis[N];
int pow2[N];
unsigned int poww[N];
int top,sta[N];
struct Node
{
int ch[2];
bool sum;
unsigned int x;
}t[N*8+N*LN*4];
void up(int u,int len)
{
t[u].sum=t[lc(u)].sum&t[rc(u)].sum;
t[u].x=t[lc(u)].x+poww[len]*t[rc(u)].x;
}
void build(int &u,int l,int r,bool val)
{
u=++node;
if(l==r)
{
t[u].sum=val;
t[u].x=val;
return;
}
int mid=(l+r)>>1;
build(lc(u),l,mid,val);
build(rc(u),mid+1,r,val);
up(u,mid-l+1);
}
int compare(int a,int b,int l,int r)
{
if(l==r)
{
if(t[a].sum==t[b].sum) return 0;
if(t[a].sum) return 1;
if(t[b].sum) return -1;
}
int mid=(l+r)>>1;
if(t[rc(a)].x!=t[rc(b)].x) return compare(rc(a),rc(b),mid+1,r);
return compare(lc(a),lc(b),l,mid);
}
int find2(int u,int l,int r)
{
if(t[u].sum) return r;
if(l==r) return -1;
int mid=(l+r)>>1;
int lans=find2(lc(u),l,mid);
if(lans==mid)
{
int rans=find2(rc(u),mid+1,r);
if(rans!=-1) return rans;
}
return lans;
}
int find1(int u,int l,int r,int x)
{
if(x<=l) return find2(u,l,r);
int mid=(l+r)>>1;
if(x<=mid)
{
int lans=find1(lc(u),l,mid,x);
if(lans==mid)
{
int rans=find1(rc(u),mid+1,r,x);
if(rans!=-1) return rans;
}
return lans;
}
return find1(rc(u),mid+1,r,x);
}
void update1(int &a,int b,int c,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
{
a=c;
return;
}
a=++node;
t[a]=t[b];
int mid=(l+r)>>1;
if(ql<=mid) update1(lc(a),lc(b),lc(c),l,mid,ql,qr);
if(qr>mid) update1(rc(a),rc(b),rc(c),mid+1,r,ql,qr);
up(a,mid-l+1);
}
void update2(int &a,int b,int l,int r,int x)
{
a=++node;
t[a]=t[b];
if(l==r)
{
t[a].sum=1;
t[a].x=1;
return;
}
int mid=(l+r)>>1;
if(x<=mid) update2(lc(a),lc(b),l,mid,x);
else update2(rc(a),rc(b),mid+1,r,x);
up(a,mid-l+1);
}
int add(int rt,int x)
{
int tmp=find1(rt,0,1e5+17,x);
int nrt1=rt;
if(tmp!=-1) update1(nrt1,rt,rt0,0,1e5+17,x,tmp);
else tmp=x-1;
int nrt2;
update2(nrt2,nrt1,0,1e5+17,tmp+1);
return nrt2;
}
struct data
{
int u,rt;
data(){};
data(int a,int b){u=a,rt=b;}
bool operator < (const data &a) const
{
return compare(rt,a.rt,0,1e5+17)>0;
}
};
priority_queue<data>q;
void adde(int u,int v,int xi)
{
to[++cnt]=v;
w[cnt]=xi;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dijkstra()
{
for(int i=1;i<=n;i++) dis[i]=rt1;
dis[S]=rt0;
q.push(data(S,dis[S]));
while(!q.empty())
{
data now=q.top();
q.pop();
if(vis[now.u]) continue;
vis[now.u]=1;
for(int i=head[now.u];i;i=nxt[i])
{
int v=to[i];
int rta=add(now.rt,w[i]);
if(compare(rta,dis[v],0,1e5+17)<0)
{
dis[v]=rta,pre[v]=now.u;
q.push(data(v,dis[v]));
}
}
}
}
int getsum(int u,int l,int r)
{
if(l==r) return t[u].sum*pow2[l];
int mid=(l+r)>>1,ans=0;
if((ans+=getsum(lc(u),l,mid))>=mod) ans-=mod;
if((ans+=getsum(rc(u),mid+1,r))>=mod) ans-=mod;
return ans;
}
int main()
{
pow2[0]=poww[0]=1;
for(int i=1;i<=1e5+17;i++)
{
pow2[i]=(pow2[i-1]<<1)%mod;
poww[i]=poww[i-1]*base;
}
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,x;
scanf("%d%d%d",&u,&v,&x);
adde(u,v,x),adde(v,u,x);
}
scanf("%d%d",&S,&T);
build(rt0,0,1e5+17,0);
build(rt1,0,1e5+17,1);
dijkstra();
if(!vis[T])
{
puts("-1");
return 0;
}
printf("%d
",getsum(dis[T],0,1e5+17));
for(int u=T;u!=S;u=pre[u]) sta[++top]=u;
sta[++top]=S;
printf("%d
",top);
for(int i=top;i>=1;i--)
printf("%d ",sta[i]);
return 0;
}
/*
2 1
1 2 1
1 2
*/