题目传送门：http://pan.baidu.com/s/1eRRG6Wy
离线版题目：http://paste.ubuntu.com/18687179/
数据传送门：http://pan.baidu.com/s/1qYtM8f6
数据生成器：http://paste.ubuntu.com/18687249/
唉，以前在CF上，看过这道题，拿到后，一眼就记得跟线段树有关，然而还是没有做出来QAQ
说一说怎么做：
如果边权很小，那么我们直接跑最短路就好，如果边权再大一点，那我们就写高精度
然而这题有2^100000，这个大概有10000那么多位（DEC），高精度会T，而且空间也开不下
所以只能搞神奇的技巧。
我们那函数式线段树来模拟二进制数组。那么单次修改就是log（n）的时间和空间复杂度
那么，比较大小怎么搞？搞一搞Hash，然后找到第一位不同的地方比较大小，仍然是log（n）
那么怎么进位？单点赋一，区间赋零即可，也为log（n）
然后就是码代码的事情了，我代码只写了一个小时，然而调试了3小时QAQ
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 200000+9;
const int MOD = 1000000000+7;
const int HASH = 9999971;
const int SEED = 137;
const int INF = 100000000;
int n,m,T,to[MAXN],head[MAXN],nxt[MAXN],cost[MAXN];
int s,t,done[MAXN],tpw[MAXN];
inline int read(){
char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}
namespace Chair_Tree{
#define CT Chair_Tree
#define N 10000000
#define MX 200000
int root[MAXN],hash[N],val[N],ch[N][2],MN[N];
int ans_tmp,cnt;
inline bool cmp(int w1, int w2){
int l=1,r=MX,mid;
while (l < r){
mid = (l+r+1)/2;
if (hash[ch[w1][1]] != hash[ch[w2][1]] || val[ch[w1][1]] != val[ch[w2][1]])
w1 = ch[w1][1], w2 = ch[w2][1], l = mid;
else w1 = ch[w1][0], w2 = ch[w2][0], r = mid-1;
}
return val[w1] > val[w2];
}
void find(int w, int l, int r, int pos){
if (!w) ans_tmp = min(ans_tmp, l);
else if (l >= pos) ans_tmp = min(ans_tmp, MN[w]);
else if (r >= pos && l < r) {
int mid = (l+r+1) / 2;
if (pos < mid) find(ch[w][0], l, mid-1, pos);
find(ch[w][1], mid, r, pos);
}
}inline int find(int w, int pos){ans_tmp = INF;find(w, 1, MX, pos);return ans_tmp;}
inline void maintain(int w, int l, int r){
int len = (l+r+1)/2-l; MN[w] = INF;
hash[w] = (LL)((LL)hash[ch[w][0]]+(LL)SEED*hash[ch[w][1]])*SEED % HASH;
val[w] = (LL)((LL)val[ch[w][0]] + (LL)val[ch[w][1]]*tpw[len]) % MOD;
if (ch[w][0]) MN[w] = min(MN[w], MN[ch[w][0]]);
else MN[w] = min(MN[w], l);
if (ch[w][1]) MN[w] = min(MN[w], MN[ch[w][1]]);
else MN[w] = min(MN[w], (l+1+r)/2);
if (l == r && !val[w]) MN[w] = min(MN[w], l);
}
void modify(int pre, int &w, int l, int r, int p){
w = ++cnt; ch[w][0] = ch[pre][0]; ch[w][1] = ch[pre][1];
if (l == r) hash[w] = 1, val[w] = 1, MN[w] = INF;
else {
int mid = (l+r+1) / 2;
if (p < mid) modify(ch[pre][0], ch[w][0], l, mid-1, p);
else modify(ch[pre][1], ch[w][1], mid, r, p);
maintain(w,l,r);
}
}
void clear(int pre, int &w, int l, int r, int L, int R){
int mid = (l+r+1) / 2;
if (L <= l && r <= R) w = 0;
else {
w = ++cnt; ch[w][0] = ch[pre][0]; ch[w][1] = ch[pre][1];
if (L < mid) clear(ch[pre][0], ch[w][0], l, mid-1, L, R);
if (R >= mid) clear(ch[pre][1], ch[w][1], mid, r, L, R);
maintain(w,l,r);
}
}
inline int Add(int rt, int pos){
int p1 = max(find(rt, pos),pos), ret;
modify(rt, ret, 1, MX, p1);
if (p1 > pos) clear(ret, ret, 1, MX, pos ,p1-1);
return ret;
}
inline void output(int rt){
printf("%d\n",val[rt]%MOD);
}
inline void print_path(){
int w = t; cout<<t<<endl;
while (w != s){
for (int i=head[w];i;i=nxt[i]){
int tmp = Add(root[to[i]], cost[i]);
if (cmp(tmp,root[w])^cmp(root[w],tmp)==0)
w = to[i], cout<<w<<' '<<val[root[w]]<<endl;
}
}
cout<<s;
}
void build(int &w, int l, int r){
w = ++cnt; MN[w] = INF;
if (l == r) hash[w] = val[w] = 1;
else {
int mid = (l+r+1)/2;
build(ch[w][0], l, mid-1);
build(ch[w][1], mid, r);
maintain(w,l,r);
}
}inline int build_Tree(){int ret; build(ret,1,MX); return ret;}
};
struct DATA{
int p,rt; DATA(){}
DATA(int P, int RT):p(P),rt(RT){}
bool operator < (const DATA &B) const {
return CT::cmp(rt, B.rt);
}
};
priority_queue<DATA> Q;
inline void AddEdge(int a, int b, int c){
to[++T] = b; nxt[T] = head[a]; head[a] = T; cost[T] = c;
to[++T] = a; nxt[T] = head[b]; head[b] = T; cost[T] = c;
}
inline void Dijkstra(){
int tmp = CT::build_Tree();
for (int i=1;i<=n;i++) CT::root[i] = tmp;
CT::root[s] = 0;
Q.push(DATA(s,CT::root[s]));
while (!Q.empty()){
DATA w = Q.top(); Q.pop();
if (done[w.p]) continue;
else if (w.p == t) {
CT::output(w.rt);return;
} else {
done[w.p] = 1;
for (int i=head[w.p];i;i=nxt[i]){
if (done[to[i]]) continue;
else {
tmp = CT::Add(w.rt,cost[i]);
if (CT::cmp(CT::root[to[i]], tmp))
CT::root[to[i]] = tmp,
Q.push(DATA(to[i], tmp));
}
}
}
}
printf("-1\n");
}
int main(){
freopen("shortest.in","r",stdin);
freopen("shortest.out","w",stdout);
n = read(); m = read();
for (int i=1,a,b,c;i<=m;i++)
a=read(), b=read(), c=read(),
AddEdge(a, b, c+1);
s = read(); t = read(); tpw[0] = 1;
for(int i=1;i<=150000;i++)
tpw[i] = (LL)tpw[i-1]*2%MOD;
Dijkstra();
return 0;
}
