跳转至

最短路相关

dijktra 单源最短路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
namespace dijkstra
{
    vector<pii> G[MAX];
    int dis[MAX],vis[MAX];
    priority_queue<pii> q;

    inline void dijkstra(int s)
    {
        memset(dis,0x3f,sizeof dis),memset(vis,0,sizeof vis);
        dis[s]=0,q.emplace(mp(0,s));
        while(!q.empty())
        {
            int now=q.top().second; q.pop();
            if(vis[now]) continue;
            vis[now]=1;
            for(auto [to,val]:G[now]) if(dis[to]>dis[now]+val) dis[to]=dis[now]+val,q.emplace(mp(-dis[to],to));
        }
    }
}

SPFA 单源最短路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
namespace SPFA
{
    vector<pii> G[MAX];
    int dis[MAX],vis[MAX];
    queue<int> q;

    inline void SPFA(int s)
    {
        memset(dis,0x3f,sizeof dis),memset(vis,0,sizeof vis);
        dis[s]=0,vis[s]=1,q.emplace(s);
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            vis[now]=0;
            for(auto [to,val]:G[now]) if(dis[to]>dis[now]+val) {dis[to]=dis[now]+val; if(!vis[to]) vis[to]=1,q.emplace(to);}
        }
    }
}

SPFA 判负环

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
namespace Check_Loop
{
    vector<pii> G[MAX];
    int dis[MAX],vis[MAX],con[MAX];
    queue<int> q;

    inline bool SPFA(int s)
    {
        memset(dis,0x3f,sizeof dis),memset(vis,0,sizeof vis),memset(con,0,sizeof con);
        dis[s]=0,vis[s]=1,q.emplace(s);
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            vis[now]=0;
            for(auto [to,val]:G[now]) if(dis[to]>dis[now]+val)
            {
                dis[to]=dis[now]+val,con[to]=con[now]+1;
                if(con[now]>=n) return 1;
                if(!vis[to]) vis[to]=1,q.emplace(to);
            }
        }
        return 0;
    }
}

Johnson全源最短路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
namespace Johnson
{
    vector<pii> G[MAX]; 
    int ans[MAX][MAX];
    int dis[MAX],vis[MAX],con[MAX]; queue<int> q;
    int Dis[MAX],Vis[MAX];          priority_queue<pii> Q;

    inline bool SPFA(int s)
    {
        while(!q.empty()) q.pop();
        memset(vis,0,sizeof vis),memset(dis,0x3f,sizeof dis),memset(con,0,sizeof con);
        vis[s]=1,dis[s]=0,q.emplace(s);
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            vis[now]=0;
            for(auto [to,val]:G[now]) if(dis[to]>dis[now]+val)
            {
                dis[to]=dis[now]+val,con[to]=con[now]+1;
                if(con[now]>=n) return 1;
                if(!vis[to]) vis[to]=1,q.emplace(to);
            }
        }
        return 0;
    }
    inline void dijkstra(int s)
    {
        memset(Vis,0,sizeof Vis),memset(Dis,0x3f,sizeof Dis);
        Dis[s]=0,Q.emplace(mp(0,s));
        while(!Q.empty())
        {
            int now=Q.top().second; Q.pop();
            if(Vis[now]) continue;
            Vis[now]=1;
            for(auto [to,val]:G[now]) if(Dis[to]>Dis[now]+val) Dis[to]=Dis[now]+val,Q.emplace(mp(-Dis[to],to));
        }
    }
    inline bool solve()
    {
        for(int i=1;i<=n;++i) G[0].eb(mp(i,0));
        if(SPFA(0)) return 1;
        for(int i=1;i<=n;++i) for(int j=0;j<((int)G[i].size());++j) G[i][j].se+=dis[i]-dis[G[i][j].fi];
        for(int i=1;i<=n;++i)
        {
            dijkstra(i);
            for(int j=1;j<=n;++j) if(Dis[j]==INF) ans[i][j]=-1; else ans[i][j]=Dis[j]+dis[j]-dis[i];
        }
        return 0;
    }
}