下面的讨论默认 \(n,m,x_i\) 同阶。
这个问题与常规 \(\tt dij\),仅仅差在高精度。而 \(\tt dij\) 所需的高精度如下:
考虑数据结构维护 \(dis\) 的二进制分解。直接维护空间是 \(\mathcal O(nx)\) 的,但是 \(dis\) 之间互相转移、取 \(\min\),必然有很多位是相同的,于是考虑主席树。
对于加法,
对于比较,
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i = (a);i <= (b);++i) using hsh = unsigned long long; const int N = 1e5 + 5; const int S = N * 60; const hsh mod = 1e9 + 7; const int X = 1e5 + 50; int n,m,s,t,rt[N],pre[N],dis[N]; bool vis[N]; vector<pair<int,int> > G[N]; hsh pow2[X + 10]; int fa[N],XX; int lc[S],rc[S],cc; hsh w[S]; bool i1[S]; #define mid ((L + R) >> 1) #define ls lc[i],L,mid #define rs rc[i],mid + 1,R void psu(int i,int L,int R){ i1[i] = i1[lc[i]] && i1[rc[i]]; w[i] = (w[rc[i]] * pow2[mid - L + 1] % mod + w[lc[i]]) % mod; } void build(int &i,int L,int R,int x){ i = ++cc; if(L == R) return void(i1[i] = w[i] = x); build(ls,x); build(rs,x); psu(i,L,R); } bool cmp(int i,int j,int L,int R){ if(L == R) return w[i] > w[j]; return w[rc[i]] == w[rc[j]] ? cmp(lc[i],lc[j],L,mid) : cmp(rc[i],rc[j],mid + 1,R); } int fnd(int i,int L,int R){ if(i1[i]) return R; if(L == R) return -1; int _ = fnd(ls); return _ == mid ? max(fnd(rs),mid) : _; } int pos(int i,int L,int R,int p){ if(p <= L) return fnd(i,L,R); if(p > mid) return pos(rs,p); int _ = pos(ls,p); return _ == mid ? max(mid,pos(rs,p)) : _; } struct node{ int u,r; node(int u = 0,int r = 0) : u(u),r(r){} bool operator<(const node &p) const { return cmp(r,p.r,0,XX); } }; void chg(int &p,int i,int j,int L,int R,int l,int r){ if(l <= L && R <= r) return void(p = j); p = ++cc; rc[p] = rc[i]; lc[p] = lc[i]; i1[p] = i1[i]; w[p] = w[i]; if(l <= mid) chg(lc[p],lc[i],lc[j],L,mid,l,r); if(r > mid) chg(rc[p],rc[i],rc[j],mid + 1,R,l,r); psu(p,L,R); } void upd(int &p,int i,int L,int R,int x){ p = ++cc; rc[p] = rc[i]; lc[p] = lc[i]; i1[p] = i1[i]; w[p] = w[i]; if(L == R) return void(i1[p] = w[p] = 1); x <= mid ? upd(lc[p],ls,x) : upd(rc[p],rs,x); psu(p,L,R); } int pls(int rt,int v){ int p = pos(rt,0,XX,v),RT = rt; if(p < 0) p = v - 1; else chg(RT,rt,::rt[0],0,XX,v,p); int ret; upd(ret,RT,0,XX,p + 1); return ret; } priority_queue<node> Q; void dij(){ build(rt[0],0,XX,0); build(rt[n + 1],0,XX,1); rep(i,1,n) rt[i] = rt[n + 1]; Q.emplace(s,rt[s] = rt[0]); while(!Q.empty()){ int u = Q.top().u,r = Q.top().r; Q.pop(); if(vis[u]) continue; vis[u] = 1; if(u == t) return; for(auto e : G[u]){ int v = e.first,w = e.second; int RT = pls(r,w); if(cmp(rt[v],RT,0,XX)){ Q.emplace(v,rt[v] = RT),pre[v] = u; dis[v] = (dis[u] + pow2[w]) % mod; } } } } void print(){ printf("%d\n",dis[t]); deque<int> P; while(t != s) P.push_front(t),t = pre[t]; P.push_front(s); printf("%d\n",P.size()); for(int x : P) printf("%d ",x); printf("\n"); } int fnd(int i){ return i == fa[i] ? i : fa[i] = fnd(fa[i]); } int main(){ scanf("%d%d",&n,&m); rep(i,1,n) fa[i] = i; rep(i,1,m){ int u,v,w; scanf("%d%d%d",&u,&v,&w); fa[fnd(u)] = fnd(v); G[u].emplace_back(v,w); G[v].emplace_back(u,w); XX = max(XX,w); } scanf("%d%d",&s,&t); if(fnd(s) != fnd(t)) return printf("-1\n"),0; pow2[0] = 1; XX += 25; rep(i,1,XX + 2) pow2[i] = (pow2[i - 1] * 2) % mod; dij(); print(); return 0; }