题目传送门：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;
}
Hello, just wanted to mention, I loved this article.
It was practical. Keep on posting!
Your mode of telling the whole thing in this article is
really pleasant, every one be capable of without difficulty be aware
of it, Thanks a lot.
You really make it seem so easy with your presentation but I find this
topic to be really something which I think I would never understand.
It seems too complicated and very broad for me.
I am looking forward for your next post, I will try to get the hang of it!
It’s really a nice and helpful piece of information. I’m happy that
you shared this helpful info with us. Please keep us informed like this.
Thank you for sharing.
I just like the helpful info you provide to your
articles. I will bookmark your weblog and
test once more right here frequently. I am fairly certain I
will learn plenty of new stuff right right here!
Best of luck for the following!
Great info. Lucky me I ran across your blog by accident (stumbleupon).
I have saved as a favorite for later!
Hey very cool website!! Man .. Excellent .. Superb ..
I will bookmark your web site and take the feeds also? I am happy to find numerous useful information here within the put up,
we want work out more strategies on this regard, thank you for sharing.
. . . . .
Greetings from Los angeles! I’m bored to death at work so I decided to check
out your website on my iphone during lunch break.
I enjoy the knowledge you present here and can’t wait to take a look when I get home.
I’m surprised at how fast your blog loaded on my cell phone ..
I’m not even using WIFI, just 3G .. Anyways, amazing blog!
This piece of writing is truly a fastidious one it
helps new web people, who are wishing in favor of blogging.
Link exchange is nothing else however it is just placing the other person’s
webpage link on your page at proper place and other person will also do
similar in favor of you.
Touche. Outstanding arguments. Keep up the amazing work.
Very quickly this web site will be famous among all blogging and site-building
users, due to it’s fastidious articles or reviews
Woah! I’m really digging the template/theme of this website.
It’s simple, yet effective. A lot of times
it’s tough to get that “perfect balance” between superb usability and visual appearance.
I must say you’ve done a awesome job with this. In addition,
the blog loads very fast for me on Chrome. Exceptional Blog!
Thanks for sharing your thoughts about how to get help in windows 10.
Regards
Wow, that’s what I was looking for, what a material!
existing here at this web site, thanks admin of this website.
Excellent web site you’ve got here.. It’s hard to find high quality writing
like yours nowadays. I truly appreciate individuals like you!
Take care!!
Greetings! I’ve been following your site for some time now and finally got the courage to
go ahead and give you a shout out from Houston Texas!
Just wanted to say keep up the great job!
That is a good tip especially to those fresh to the blogosphere.
Simple but very accurate information… Thanks for sharing this one.
A must read post!
Wow, this article is good, my sister is analyzing these things, thus I am
going to tell her.
Very quickly this web site will be famous
amid all blogging and site-building visitors, due to it’s pleasant articles or reviews
Thanks for the marvelous posting! I seriously enjoyed reading it, you will
be a great author.I will make sure to bookmark your blog and will eventually come back from now on. I want to encourage you continue your great writing, have a nice afternoon!
Quality articles is the key to be a focus for the
people to go to see the web site, that’s what this site is providing.
Thanks a lot for sharing this with all folks you actually recognise
what you are speaking about! Bookmarked. Please additionally visit my site =).
We can have a hyperlink alternate contract between us
You need to be a part of a contest for one of the highest quality blogs on the internet.
I most certainly will highly recommend this site!