【BZOJ 2125】最短路

Qizy 仙人掌, 树, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2125

仙人掌上求最短路
先搞成树，然后树怎么搞，这题就怎么搞

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;
 
const int MAXN = 10000+9;
 
int n,m,Q,lowlink[MAXN],num[MAXN],dis[MAXN],nxt[MAXN*4],to[MAXN*4],head[MAXN],cost[MAXN*4];
int ring_cnt,fa[MAXN][16],dep[MAXN],length[MAXN],ring_num[MAXN],ori[MAXN],que[MAXN],fro;
vector<int> rings[MAXN];
 
inline int read(){
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline void AddEdge(int a, int b, int c){
    static int T = 0;
    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;
}
 
void DFS(int w, int f){
    static int T = 0; fa[w][0] = f;
    lowlink[w] = num[w] = ++T; que[++fro] = w;
    for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
        if (!num[to[i]]) {
            DFS(to[i], w);
            if (lowlink[to[i]] > num[w]) fro--;
            else if (lowlink[to[i]] < num[w]) lowlink[w] = lowlink[to[i]];
            else {
                ring_cnt++; int nw = que[fro--];
                while (nw != w) {
                    rings[ring_cnt].push_back(nw);
                    nw = que[fro--];
                }   
                rings[ring_cnt].push_back(w); que[++fro] = w;
            }
        } else lowlink[w] = min(lowlink[w], num[to[i]]);
    }
}
 
inline void prework(){
    for (int k=1;k<=ring_cnt;k++) {
        int size = rings[k].size();
        int rt = rings[k][size-1],tmp=0;
         
        for (int i=1;i<=size;i++) que[i] = rings[k][i-1];
        que[0] = rt; que[size+1] = que[1];
        for (int i=1;i<size;i++) ring_num[que[i]] = k, fa[que[i]][0] = rt;
         
        for (int i=1;i<=size;i++) {
            for (int j=head[que[i]];j;j=nxt[j]) {
                if (to[j] == que[i-1]) to[j] = 0, tmp += cost[j];
                else if (to[j] == que[i+1]) to[j] = 0;
            }
            ori[que[i]] = tmp;
        } ori[rt] = 0; length[k] = tmp;
        for (int i=1;i<size;i++) AddEdge(rt,que[i],min(ori[que[i]], tmp-ori[que[i]]));
    }
}
 
void GetDis(int w){
    for (int i=head[w];i;i=nxt[i]) if (!dis[to[i]] && to[i]) 
        dis[to[i]]=dis[w]+cost[i], dep[to[i]] = dep[w] + 1, GetDis(to[i]);
}
 
inline void LCA_init() {
    for (int k=1;k<=15;k++) for (int i=1;i<=n;i++) 
        fa[i][k] = fa[fa[i][k-1]][k-1];
}
 
inline int LCA(int a, int b, int &l1, int &l2){
    if (dep[a] < dep[b]) swap(a,b);
    for (int k=15;~k;k--) if (dep[fa[a][k]] >= dep[b]) a = fa[a][k];
    l1 = l2 = a;
    if (a == b) return a;
    else {
        for (int k=15;~k;k--) if (fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
        l1 = a, l2 = b; return fa[a][0];
    }
}
 
int main(){
    n = read(); m = read(); Q = read();
    for (int i=1,a,b,c;i<=m;i++) 
        a = read(), b = read(), c = read(),
        AddEdge(a, b, c);
    DFS(1,0); prework();
    dis[1] = dep[1] = 1; GetDis(1); LCA_init();
    for (int i=1,a,b,r,lca1,lca2;i<=Q;i++){
        a = read(); b = read();
        r = LCA(a, b, lca1, lca2);
        if (ring_num[lca1] && ring_num[lca1] == ring_num[lca2]) {
            int len = abs(ori[lca1]-ori[lca2]);
            len = min(len, length[ring_num[lca1]]-len);
            printf("%d\n",dis[a]-dis[lca1]+dis[b]-dis[lca2]+len);
        } else printf("%d\n",dis[a]+dis[b]-2*dis[r]);
    }
    return 0;
}

另外，这份代码在预处理环那里有问题
会被一个点连了几个环的情况卡成翔
正确的写法，参见BZOJ_1023

305 thoughts to “【BZOJ 2125】最短路”

  3. Simply want to say your article is as astonishing. The clearness in your submit
    is just spectacular and that i can suppose you are a professional
    on this subject. Well along with your permission allow me to
    seize your RSS feed to stay up to date with impending post.

    Thanks a million and please continue the rewarding work.

    Reply

  4. At this time it seems like Expression Engine is the best blogging platform available right now.
    (from what I’ve read) Is that what you’re using on your blog?

    Reply

  6. You really make it seem so easy with your presentation but
    I find this topic to be really something that I think I would never understand.
    It seems too complex and very broad for me. I am looking forward for
    your next post, I’ll try to get the hang of it!

    Reply

  8. An impressive share! I have just forwarded this onto a colleague who has been conducting
    a little homework on this. And he actually ordered me breakfast simply because I found it for
    him… lol. So allow me to reword this…. Thanks for
    the meal!! But yeah, thanx for spending time to discuss this
    topic here on your website.

    Reply

  9. I have been surfing online more than three hours
    today, yet I never found any interesting article like yours.
    It is pretty worth enough for me. In my view, if all website owners and bloggers made good content
    as you did, the internet will be much more useful than ever before.

    Reply

  10. Howdy just wanted to give you a quick heads up and let you know
    a few of the pictures aren’t loading correctly. I’m
    not sure why but I think its a linking issue.
    I’ve tried it in two different browsers and both show the same results.

    Reply

  14. Appreciating the hard work you put into your blog
    and in depth information you provide. It’s good to
    come across a blog every once in a while that isn’t the same out of date rehashed material.
    Great read! I’ve saved your site and I’m including your
    RSS feeds to my Google account.

    Reply

  15. I know this website offers quality dependent articles and extra
    information, is there any other website which presents these kinds of stuff in quality?

    Reply

  18. Hi there just wanted to give you a brief heads up and let you know
    a few of the images aren’t loading properly. I’m not sure why
    but I think its a linking issue. I’ve tried it
    in two different web browsers and both show
    the same results.

    Reply

  21. Its like you read my mind! You appear to know so much about this, like you
    wrote the book in it or something. I think that you can do with some pics to drive the message
    home a bit, but instead of that, this is magnificent blog.

    A great read. I will certainly be back.

    Reply

  23. Do you mind if I quote a couple of your articles
    as long as I provide credit and sources back to your site?
    My website is in the exact same niche as yours and my users would truly
    benefit from a lot of the information you provide here.

    Please let me know if this alright with you. Thanks!
    natalielise pof

    Reply

  25. Good day! This is my 1st comment here so I just wanted to give a quick
    shout out and tell you I really enjoy reading
    your posts. Can you recommend any other blogs/websites/forums that
    go over the same subjects? Thank you! natalielise pof

    Reply

  26. Link exchange is nothing else however it is just placing the other
    person’s website link on your page at appropriate place and other person will also do same for you.

    Reply

  27. Hello, I think your site might be having browser compatibility issues.
    When I look at your website in Safari, it looks fine however when opening in I.E., it’s
    got some overlapping issues. I simply wanted to give you a quick heads up!

    Besides that, wonderful blog!

    Reply

  29. I am genuinely delighted to glance at this weblog posts which carries plenty of useful
    data, thanks for providing these kinds of statistics.

    Reply

  30. I have been surfing on-line more than three hours today, yet I by no means found any fascinating article like yours.
    It is lovely worth sufficient for me. In my opinion, if all webmasters and
    bloggers made good content material as you probably did, the web will likely be much
    more helpful than ever before. plenty of fish natalielise

    Reply

  32. I am not sure where you are getting your information, but good topic.
    I needs to spend some time learning much more or understanding more.

    Thanks for excellent information I was looking for this info for
    my mission.

    Reply

  35. I am not sure where you are getting your information, but
    good topic. I needs to spend some time learning
    much more or understanding more. Thanks
    for wonderful info I was looking for this info for my mission.

    Reply

  36. Greetings, I do think your website could be having web browser compatibility issues.
    Whenever I take a look at your web site in Safari, it looks fine however, when opening in I.E.,
    it has some overlapping issues. I simply wanted to provide you
    with a quick heads up! Other than that, fantastic website!

    Reply

  37. Thank you for any other fantastic post. Where else could anybody get that kind of information in such a perfect way of writing?
    I have a presentation subsequent week, and I’m at the look for such info.

    Reply

  38. Somebody essentially help to make severely posts I’d state.
    That is the first time I frequented your website page and
    thus far? I amazed with the analysis you made to create this actual post incredible.

    Fantastic job!

    Reply

  41. My brother recommended I may like this website. He
    was entirely right. This submit actually made
    my day. You cann’t believe simply how so much time I had spent for this info!
    Thanks!

    Reply

  43. Howdy! I’m at work browsing your blog from my new iphone!
    Just wanted to say I love reading through your blog and look forward
    to all your posts! Keep up the great work!

    Reply

  44. I believe this is one of the most vital information for me.

    And i am happy reading your article. But want to statement on some normal issues, The website style is perfect, the articles is truly excellent :
    D. Excellent job, cheers

    Reply

  46. Howdy I am so grateful I found your site, I
    really found you by accident, while I was researching on Askjeeve for
    something else, Regardless I am here now and would just like to say
    thank you for a incredible post and a all round enjoyable blog (I
    also love the theme/design), I don’t have time to look over it
    all at the moment but I have saved it and also added in your
    RSS feeds, so when I have time I will be back to read a lot more, Please do keep up
    the superb work.

    Reply

  47. Hello, i read your blog from time to time and i own a similar one and i was just
    curious if you get a lot of spam comments? If so how do you reduce
    it, any plugin or anything you can suggest? I get so much lately it’s driving me crazy so
    any help is very much appreciated.

    Reply

  48. Howdy just wanted to give you a quick heads up and let you know a few of the images
    aren’t loading properly. I’m not sure why but I think its a linking
    issue. I’ve tried it in two different web browsers and both show
    the same outcome.

    Reply

  50. Excellent blog right here! Additionally your website lots up very fast!
    What web host are you using? Can I am getting your associate hyperlink to your host?
    I wish my site loaded up as fast as yours lol

    Reply

  52. Thank you for every other informative web site.

    Where else could I am getting that type of information written in such a perfect
    means? I have a venture that I’m simply now working on, and I have been on the
    look out for such information.

    Reply

  56. Hey there! This post couldn’t be written any better! Reading
    through this post reminds me of my old room mate!
    He always kept chatting about this. I will forward this article to him.
    Pretty sure he will have a good read. Many thanks for sharing!

    Reply

  57. May I just say what a relief to uncover a person that truly understands what they’re talking about on the web.
    You actually know how to bring an issue to light and make it important.

    More people really need to check this out and understand this side of your story.
    I was surprised that you are not more popular given that you surely have the gift.

    Reply

  60. Hello there I am so happy I found your blog, I really found you by mistake, while I was researching on Digg for something else, Anyhow I
    am here now and would just like to say kudos for a incredible post and a all
    round thrilling blog (I also love the theme/design), I don’t have time to read through
    it all at the moment but I have book-marked it and also added in your RSS feeds, so when I have time I will be back to read more, Please
    do keep up the awesome job.

    Reply

  62. Hi are using WordPress for your site platform? I’m new to the blog world but I’m trying to get
    started and create my own. Do you require any html coding expertise to make your own blog?

    Any help would be really appreciated!

    Reply

  67. Thanks , I’ve just been looking for info about this subject for a while and yours is the best I have discovered
    so far. However, what about the bottom line?
    Are you certain about the supply?

    Reply

  90. hello there and thank you for your info – I have definitely picked up anything new from right here.

    I did however expertise a few technical points using this
    site, since I experienced to reload the website
    a lot of times previous to I could get it to load
    properly. I had been wondering if your hosting is OK? Not that I am complaining, but slow loading instances times will very frequently affect your placement in google and could damage your high-quality score if ads and marketing with Adwords.

    Well I’m adding this RSS to my e-mail and could look out for a lot more of
    your respective intriguing content. Ensure that you update this again soon.

    Reply

  100. It’s a shame you don’t have a donate button! I’d most certainly
    donate to this fantastic blog! I suppose for now i’ll settle for book-marking and adding your RSS feed to
    my Google account. I look forward to brand new updates and will talk about this blog with my Facebook group.
    Chat soon!

    Reply

  112. Hey would you mind letting me know which webhost you’re utilizing?
    I’ve loaded your blog in 3 different browsers and I must
    say this blog loads a lot faster then most. Can you recommend a good internet hosting provider at a fair
    price? Thanks a lot, I appreciate it!

    Reply

  116. I like the valuable information you provide in your
    articles. I’ll bookmark your blog and check again here frequently.
    I am quite sure I will learn lots of new stuff right here!
    Good luck for the next!

    Reply

  122. I really love your site.. Pleasant colors & theme.

    Did you create this website yourself? Please reply back as I’m planning to create my
    own blog and would love to learn where you got this from or just what the theme is named.

    Kudos!

    Reply

  131. Hey there would you mind sharing which blog platform you’re working with?

    I’m planning to start my own blog in the near future but
    I’m having a difficult time selecting between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design seems different then most blogs and I’m
    looking for something completely unique.
    P.S My apologies for getting off-topic but I had to
    ask!

    Reply

  133. You’re so awesome! I don’t think I’ve read anything like that before.
    So nice to discover someone with genuine thoughts on this subject matter.
    Seriously.. thank you for starting this up. This website is one thing that’s needed on the internet, someone with a little originality!

    Reply

  141. hey there and thank you for your information – I have certainly picked up something new from right here.
    I did however expertise some technical issues using this site, as I experienced to
    reload the site a lot of times previous to I could get it to load correctly.

    I had been wondering if your web host is OK? Not
    that I’m complaining, but slow loading instances
    times will often affect your placement in google and can damage your high-quality score if ads and marketing with Adwords.
    Anyway I am adding this RSS to my e-mail and can look out for much
    more of your respective interesting content.
    Make sure you update this again soon.

    Reply

  238. It is the best time to make a few plans for the long run and
    it is time to be happy. I’ve learn this post and if I may just I want to counsel you some fascinating
    issues or advice. Maybe you could write next articles regarding this article.
    I want to learn more issues approximately it!

    Reply

  264. Thank you for some other informative blog. The place else may I get that kind of info written in such an ideal way? I have a undertaking that I’m just now operating on, and I have been on the look out for such info.|

    Reply

  272. Hi there, I discovered your web site by way of Google even as looking for a similar matter, your site got here up, it looks good. I’ve bookmarked it in my google bookmarks.

    Reply

  284. We stumbled over here by a different web address and thought I might check things out. I like what I see so now i’m following you. Look forward to exploring your web page for a second time.|

    Reply

  285. What i do not understood is actually how you’re now not actually a lot more neatly-appreciated than you might be now. You’re very intelligent. You realize thus considerably with regards to this topic, produced me for my part imagine it from a lot of various angles. Its like women and men aren’t fascinated unless it’s one thing to accomplish with Woman gaga! Your own stuffs great. Always care for it up!|

    Reply

  298. Wow, superb weblog layout! How lengthy have you been blogging for? you make running a blog look easy. The overall look of your site is fantastic, as well as the content!

    Reply

  305. Woah! I’m really loving the template/theme of this site. It’s simple, yet effective. A lot of times it’s very difficult to get that “perfect balance” between superb usability and visual appearance. I must say that you’ve done a fantastic job with this. Additionally, the blog loads super quick for me on Firefox. Superb Blog!|

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *