Johnson全源最短路 – Zechel

由于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);
    }
}

 

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

  1. 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&amp;
    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

  2. 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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

川公网安备 51130202000337号