CF 传送门：CF464E The Classic Problem
首先在此感谢 @orz_z 和 @Albert_van 两个大佬的学术支持。
Solution
最短路 + 主席树。
最短路不用说了，主要考虑如何计算那些 2 的若干次方的边权。维护边权不太可行，我们维护最短路中到每一个节点的最近距离 dis_i。数据实在太大了，高精度显然不行。
往数据结构方面想，发现若是对一个节点的 dis_i 建一棵线段树，我们要在上面维护什么。显然，只有相加和比大小。线段树的每一位代表数值二进制上的每一位，初始全为 0。
-
相加：
由于都是 2 的若干次方，所以相加的时候，不妨记加上 2^x，实际上就是将从第 x 为开始的、向前的、连续的若干个 1 全部更改为 0，然后在这些 0 前面加 1。换言之，区间修改 + 单点修改。那比大小呢？对于线段树中的每个区间，我们都维护这个区间所组成的数的数值，维护方式是哈希。
-
比大小：
对于两个相同长度的不同区间，不能直接比较两者的哈希值，因为哈希只能确定两个区间相同，但无法比大小。所以我们要找到两个区间的最长相同前缀的后一位，根据这一位来确定两个区间的大小关系。
因为是跑最短路，所以每个节点 i 的 dis 值是由某一个与自己直接联通的节点松弛而来的（起点除外），故使用主席树。
最后记录路径较简单，不细说。
Code
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
#define ls(x) t[x].ls
#define rs(x) t[x].rs
#define s(x) t[x].sum
#define sz(x) t[x].sz
#define h(x) t[x].hsh
#define gmd mid=l+r>>1
const int maxn = 1e5 + 100, N = 1e5 + 20, mod = 1e9 + 7;
int n, m, S, T, tot, u, v, w;
int pw[maxn], rt[maxn], cnt, hd[maxn], pre[maxn], ot[maxn];
bool vis[maxn];
struct node{
int to, nxt, w;
}e[maxn << 1];
struct tree{
int ls, rs, sum, sz; ll hsh;
}t[maxn * 77];
inline void add(int u, int v, int w){
cnt++; e[cnt].to = v, e[cnt].nxt = hd[u], e[cnt].w = w, hd[u] = cnt;
}
inline void up(int x){
s(x) = s(ls(x)) + s(rs(x));
h(x) = (pw[sz(ls(x))] * h(rs(x)) % mod + h(ls(x))) % mod;
}
inline void build(int &x, int l, int r){
x = ++tot, sz(x) = r - l + 1;
if(l == r) return;
int mid = l + r >> 1; build(ls(x), l, mid), build(rs(x), mid + 1, r), up(x);
}
inline void upp(int &x, int lst, int l, int r, int pos){
x = ++tot, t[x] = t[lst];
if(l == r) {s(x) += 1, h(x) += 1; return;}
int mid = l + r >> 1; if(pos <= mid) upp(ls(x), ls(lst), l, mid, pos); else upp(rs(x), rs(lst), mid + 1, r, pos); up(x);
}
inline void upr(int &x, int lst, int init, int l, int r, int L, int R){
if(l >= L and r <= R) {x = init; return;}
x = ++tot, t[x] = t[lst]; int mid = l + r >> 1;
if(L <= mid) upr(ls(x), ls(lst), ls(init), l, mid, L, R); if(R > mid) upr(rs(x), rs(lst), rs(init), mid + 1, r, L, R); up(x);
}
inline int qry(int x, int l, int r, int L, int R){
if(l >= L and r <= R) return s(x); int mid = l + r >> 1;
return (L <= mid ? qry(ls(x), l, mid, L, R) : 0) + (R > mid ? qry(rs(x), mid + 1, r, L, R) : 0);
}
inline int fnd(int x, int l, int r, int p, int num){
if(l == r) return l; int mid = l + r >> 1;
if(s(ls(x)) >= mid - p + 1 + num) return fnd(rs(x), mid + 1, r, p, num - s(ls(x))); else return fnd(ls(x), l, mid, p, num);
}
inline void mdf(int &x, int lst, int w){
int c = w > 0 ? qry(lst, 0, N, 0, w - 1) : 0;int y = fnd(lst, 0, N, w, c);
if(y > w) upr(x, lst, rt[0], 0, N, w, y - 1); else x = lst;
upp(x, x, 0, N, y);
}
inline bool cmp(int a, int b, int l, int r){
if(l == r) return s(a) > s(b); int mid = l + r >> 1;
if(h(rs(a)) == h(rs(b))) return cmp(ls(a), ls(b), l, mid);
return cmp(rs(a), rs(b), mid + 1, r);
}
inline void Pre(){
pw[0] = 1; rep(i, 1, N - 1) pw[i] = pw[i - 1] * 2ll % mod;
}
struct que{
int id, rt;
bool operator <(const que &tt) const{return cmp(rt, tt.rt, 0, N);}
}; priority_queue<que> q;
inline void dijkstra(){
build(rt[0], 0, N), rt[S] = rt[0], q.push({S, rt[S]});
while(!q.empty()){
int u = q.top().id; q.pop();
if(vis[u]) continue; vis[u] = 1;
if(u == T) break;
for(int v, i = hd[u]; i; i = e[i].nxt){
mdf(rt[n + 1], rt[u], e[i].w);
if(!rt[v = e[i].to] or cmp(rt[v], rt[n + 1], 0, N)){
rt[v] = rt[n + 1], pre[v] = u; if(!vis[v]) q.push({v, rt[v]});
}
}
}
}
signed main(){
Pre(), scanf("%d%d", &n, &m);
rep(i, 1, m) scanf("%d%d%d", &u, &v, &w), add(u, v, w), add(v, u, w);
scanf("%d%d", &S, &T), dijkstra();
if(!vis[T]){printf("-1\n"); return 0;} else printf("%lld\n", h(rt[T]));
int p; p = ot[++ot[0]] = T;
while(p != S)
p = pre[p], ot[++ot[0]] = p;
printf("%d\n", ot[0]);
for(int i = ot[0]; i; i--) printf("%d ", ot[i]);
return 0;
}
```
------------
感谢阅读。