Johnson全源最短路

发表于： 9月 19, 2020 9月 19, 2020
分类：算法笔记

由于dijkstra不能用于带有负边权的图，而Floyd算法的复杂度又过高，在处理稀疏图时往往耗时较久。

解决的方案是，使在有负边而无负环的情况下，依然可以使用dijkstra算法。

所谓的Johnson算法，其实就是在执行dijkstra算法之前，先执行一边Bellman-ford算法，通过外加一个点，给所有的原点赋一个相对值，这样既可以使负边消失，又如同重力势能一样，只改变相对值，可以在最后计算的时候复原。

需要注意的点：

1.为了使速度更快，我们使用Bellman-ford算法的堆优化版本，即SPFA算法。在判断是否存在负环的同时就能计算出每一点的相对值

2.添加的这个点，将和每一个原点之间连接一条边权为0的有向边，保证了图是连通的，同时，在判断负环时，判断条件所需要的n也要变成n+1看待

给出模板

#include <bits/stdc++.h>
#define maxn 3005
using namespace std;
inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while('0' <= ch && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}
typedef pair<long long,int>P;
int n,m;
struct edge
{
    int to;
    long long cost;
};
vector<edge>Q[maxn];
priority_queue<P,vector<P>, greater<P> >G;
long long d[maxn],h[maxn];
queue<int>SF;
int cnt[maxn],v[maxn];
void pre(int s)
{
    fill(d,d+maxn,1000000000);
    d[s]=0;
    G.push(P(0,s));
    while(!G.empty())
    {
        P e=G.top();G.pop();
        int h=e.second;
        if(d[h]<e.first)continue;
        for(int j=0;j<Q[h].size();j++)
        {
            edge y=Q[h][j];
            if(d[y.to]>d[h]+y.cost)
            {
                d[y.to]=d[h]+y.cost;
                G.push(P(d[y.to],y.to));
            }
        }
    }
}
bool check(int k)
{
    fill(h,h+maxn,100000000000000000ll);
    h[k]=0;
    SF.push(k);
    v[k]=1;
    while(!SF.empty())
    {
        int x=SF.front();
        SF.pop();
        v[x]=0;
        for(int i=0;i<Q[x].size();i++)
        {
            int y=Q[x][i].to;
            if(h[y]>h[x]+Q[x][i].cost)
            {
                h[y]=h[x]+Q[x][i].cost;
                cnt[y]=cnt[x]+1;
                if(cnt[y]>n)return false;
                if(!v[y])SF.push(y),v[y]=1;
            }
        }
    }
    return true;
}
int main()
{
    int k;
    n=read(),m=read();
    int u,v;
    long long w;
    for(int i=0;i<m;i++)
    {
        u=read(),v=read(),w=read();
        Q[u].push_back((edge){v,w});
    }
    for(int i=1;i<=n;i++)Q[0].push_back((edge){i,0});
    if(!check(0))
    {
        printf("-1");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<Q[i].size();j++)
        {
            Q[i][j].cost+=(h[i]-h[Q[i][j].to]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        pre(i);
        long long ans=0;
        for(int j=1;j<=n;j++)
        {

            if(d[j]==1000000000)ans=ans+j*d[j];
            else ans=ans+j*(d[j]+h[j]-h[i]);
        }
        printf("%lld\n",ans);
    }
}

itandsoon

15 对 “Johnson全源最短路”的想法；

IdioliInvoigo说道：

10月 14, 2020 12:12 下午

11890 amazing brunette chick in stockings adria rae gets her cunt https://foodexpo-demo.expocentre.online/index/out/?type=banner&url=michelejullian.info%2fpussy%2f16242-amazing-looking-blonde-teen-gets-her-pussy-filled.php&page=&sponsor=454
17891 tushy jade jantzen in roommates with christian clay http://www.woonsocketfirefighters.org/mobile/index.cfm?action=page&section=25&pagenum=128&href=https%3a%2f%2fmichelejullian.info%2fstockings%2f8217-leggy-natural-blondie-strips-off-her-cute-uniform-revealing-naked-teen.php
9685 blonde secretary rides dick pichunter https://wpcompresscomfa428.zapwp.com/q:lossless/retina:false/webp:true/w:480/url:michelejullian.info/amateur/25166-amateur-brought-her-for-two-reasons.php
15243 this anal babe aletta ocean having hardcore threesome sex with two http://e-avkorea.com/shop/proc/indb.cart.tab.php?action=ok&tab=today&type=delete&returnUrl=https%3a%2f%2fmichelejullian.info%2fmilf%2f17519-fresh-teens-like-threesomes.php&idx=0
9366 amazing redhead babe demonstrating her gaping asshole http://bestblackhatforum.com/redirector.php?https://michelejullian.info/tits/22583-girl-sexy-lingerie-denise-milani-breast.php
21753 nice teen yasmine gold fucking with her older boyfriend http://masciinnoversity.com/?wptouch_switch=desktop&redirect=https%3a%2f%2fmichelejullian.info%2fmilf%2f5039-hot-milf-roni-ford-flashing-her-tits-in-the-car.php
23803 hot pissing hotpissing model thousands of outdoor premium http://storebatterys.com/trigger.php?r_link=https%3a%2f%2fmichelejullian.info%2fstockings%2f12963-haley-reed-takes-off-her-sexy-lingerie-and-fishnet-stockings-spreads.php
85 mona wales hot wife enjoys her young neighbors wal http://lazurnayadoska.com/redirect/?go=michelejullian.info/ass/2680-white-teen-haileey-james-ends-up-with-jizz-on-her-chin-after-fucking.php
19062 blonde hottie aj applegate fucks two big hard cocks coed che https://delawareshorefh.mynetworksolutions.mobi/analytics/hit.php?nocache=1573802824.459&r=cutepix.info%2fsex%2friley-reyes.php&a=3&i=8926262&r2=https%3a%2f%2fmichelejullian.info%2fmature%2f12362-ebony-female-yasmine-de-leon-gets-gangbanged-and-facialized-by-good.php
21483 russian elena koshka suck dick and squirts twice during fuck http://www.microchipfiemme.it/public/contaclick/redirect.asp?url=https://michelejullian.info/hardcore/8672-doghousedigital-alexis-texas-mark-davis-kyle-stone-sexcam.php
746 blacked jia lissa beach pornhd banged by publicporn http://nycommunitybank.net/__media__/js/netsoltrademark.php?d=michelejullian.info/stockings/11937-big-tits-blonde-in-boots-shows-off-her-enormous-erection.php
364 hot pussies teens lick girls nude horny bed three http://www.m2m2.ru/extlink.php?url=michelejullian.info/pussy/23938-queens-starring-brandy-smile.php&
7879 monsters of cock hot big tits brunette fucks with huge coc http://www.alhaya.ps/ads_server/www/delivery/ck.php?oaparams=2__bannerid=13__zoneid=3__cb=061873e490__oadest=https%3a%2f%2fmichelejullian.info%2famateur%2f21319-michelle-can-hard-anal-sex-and-no-bytes.php
24998 janice posing in the bathroom on table http://active-intelligence.org/__media__/js/netsoltrademark.php?d=michelejullian.info/teen/11611-asian-coed-with-slim-physique-is-posing-and-stripping.php
16006 big boobed teen jannine makes out with an old dude gustavo https://www.audioauthority.com/javascript/pdf/viewer/viewer.php?pdf=https://michelejullian.info/babe/8091-shemale-yum-larger-lotsa-girls.php
4444 asian teen spreads her pussy lips after playing with dildo https://peters-teahouse.it/home/changeLanguage?lang=EN&returnUrl=https%3a%2f%2fmichelejullian.info%2fbrunette%2f21112-sweet-brunette-teen-gets-her-tight-anal-hole-pumped.php
4026 beautiful suicide girl allis wanna be your masterpiece http://gurigi.org/__media__/js/netsoltrademark.php?d=michelejullian.info/lesbian/11750-amateur-lesbian-girls-jana-puff-romana-ass-fucking-doggystyle.php
12636 cute wild teen riley reid gargles load of hot fresh cum after pov http://markfirstco.com/__media__/js/netsoltrademark.php?d=michelejullian.info/teen/8585-flame-magic-pink-wet-beauty-girls.php
24512 young blond homemodel starly teen http://freecos.net/shop/bannerhit.php?bn_id=308&url=https%3a%2f%2fmichelejullian.info%2flove%2f19121-two-slutty-punk-girls-jaded-and-cadence-don-need-guy.php
5630 amateur milf in fishnet top https://kik27.ru/bitrix/redirect.php?event1=news_out&event2=%2Fupload%2Fiblock%2F997%2F%D1%EC%E5%F2%E0+%CA%C3%CA%D3+%D4%EE%ED%E4+%E8%EC%F3%F9%E5%F1%F2%E2%E0+%D5%E0%E1%E0%F0%EE%E2%F1%EA%EE%E3%EE+%EA%F0%E0%FF+%ED%E0+2015+%E3%EE%E4.pdf&event3=%D1%EC%E5%F2%E0+%CA%C3%CA%D3+%D4%EE%ED%E4+%E8%EC%F3%F9%E5%F1%F2%E2%E0+%D5%E0%E1%E0%F0%EE%E2%F1%EA%EE%E3%EE+%EA%F0%E0%FF+%ED%E0+2015+%E3%EE%E4.pdf&goto=https%3a%2f%2fmichelejullian.info%2fmilf%2f14374-ass-archives-of-upskirt-jerk.php

回复
sikis izle说道：

11月 12, 2020 2:46 下午

If you want to use the photo it would also be good to check with the artist beforehand in case it is subject to copyright. Best wishes. Aaren Reggis Sela

回复
erotik说道：

11月 13, 2020 3:46 上午

You are my inspiration , I own few web logs and infrequently run out from to brand. Jolynn Court Abbye

回复
sikis izle说道：

11月 13, 2020 7:05 下午

Greate article. Keep writing such kind of information on your blog. Peri Les Lipp

回复
porno说道：

11月 14, 2020 5:15 上午

I am really happy to read this webpage posts which consists of lots of helpful facts, thanks for providing such data. Romy Alessandro Maurili

回复
erotik说道：

11月 14, 2020 5:17 上午

Helpful information. Lucky me I found your web site by accident, and I am stunned why this twist of fate did not came about earlier! I bookmarked it. Fannie Tirrell Forward

回复
erotik说道：

11月 14, 2020 12:52 下午

You are my intake , I own few blogs and occasionally run out from to brand. Anthe Paquito Dora

回复
sikis izle说道：

11月 14, 2020 4:54 下午

Wow, this paragraph is nice, my younger sister is analyzing these kinds of things, so I am going to convey her. Marlena Merle Fabiolas

回复
sikis izle说道：

11月 14, 2020 4:56 下午

There may be noticeably a bundle to learn about this. I assume you made certain good points in features also. Anet Lewiss Milon

回复
erotik说道：

11月 14, 2020 9:57 下午

I have been checking out some of your stories and i must say nice stuff. I will definitely bookmark your website. Tersina Ancell Sackey

回复
erotik说道：

11月 15, 2020 9:10 上午

Merely wanna remark that you have a very decent web site , I like the layout it really stands out. Stace Swen Edva

回复
sikis izle说道：

11月 15, 2020 4:02 下午

I really enjoy the blog article. Really thank you! Want more. Emlynne Emmerich Delanos

回复
erotik说道：

11月 15, 2020 7:22 下午

If your readers see a large, ongoing length of text, they are apt to move on. Oralee Ivar Hutchins

回复
erotik说道：

11月 15, 2020 7:24 下午

I think you have noted some very interesting points, appreciate it for the post. Deeann Yuma Wertheimer

回复
sikis izle说道：

11月 16, 2020 1:15 上午

Because the admin of this website is working, no question very soon it will be well-known, due to its quality contents. Nanette Avigdor Wavell

回复

itandsoon

15 对 “Johnson全源最短路”的想法；

发表评论 取消回复

发表评论取消回复