最短路

约 113 个字 126 行代码 预计阅读时间 2 分钟

需要来回的可以把边权乘2，多起点多终点可以建源点汇点，点权变成连向源点汇点的边权，然后由汇点做最短路

dij，当一个点出列时，它肯定是在最短路上了，若在其进队时带上边编号，则可以在其出列时知道最短路径树的边

dij做最短路计数不能处理边权0的情况

namespace floyd
{
    int n;
    ll dis[N][N];
    void init(int m)
    {
        n=m;
        for(int i=0;i<=n;++i)
        {
            for(int j=0;j<=n;++j)
                dis[i][j]=0;
        }
    }
    void flo()
    {
        for(int k = 1; k <= n; ++k)
        {
            for(int i = 1; i <= n; ++i)
            {
                for(int j = 1; j <= n; ++j)
                {
                    if(dis[i][j] > dis[i][k] + dis[k][j])
                        dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
};
namespace dijkstra
{
    struct edge
    {
        int v;
        ll w;
        bool operator>(const edge &b)const
        {
            return w>b.w;
        }
    };
    int n,vis[N];
    ll dis[N];
    vector<edge> e[N];
    priority_queue<edge,vector<edge>,greater<edge> > q;
    void add_edge(int u,int v,ll w)
    {
        e[u].push_back({v,w});
        // e[v].push_back({u,w});
    }
    void run(int begin)
    {
        memset(dis,0x3f,sizeof(dis[0])*(n+1));
        memset(vis,0,sizeof(int)*(n+1));
        dis[begin]=0;
        q.push({begin,0});
        int u,v;
        while(!q.empty())
        {
            u=q.top().v;
            q.pop();
            if(vis[u])
                continue;
            vis[u]=1;
            for(edge &ed:e[u])
            {
                v=ed.v;
                if(dis[v]<=dis[u]+ed.w)
                    continue;
                dis[v]=dis[u]+ed.w;
                q.push({v,dis[v]});
            }
        }
    }
    void init(int nn)
    {
        n=nn;
        for(int i=0;i<=n;++i)
            e[i].clear();
    }
};
namespace bellmanFord
{
    struct edge
    {
        int u,v;
        ll w;
    };
    int n,tot;
    ll dis[N];
    edge e[M];
    void init(int nn,int begin)
    {
        n=nn;
        tot=0;
        for(int i=0;i<=n;++i)
            dis[i]=INF;
        dis[begin]=0;
    }
    void add_edge(int u,int v,ll w)
    {
        e[++tot]={u,v,w};
    }
    bool bf() 
    {
        int f=1;
        for(int i=0;i<n-1 && f;++i)
        {
            f=0;
            for(int j=1;j<=tot;++j)
            {
                if(dis[e[j].v]>dis[e[j].u]+e[j].w)
                {
                    dis[e[j].v]=dis[e[j].u]+e[j].w;
                    f=1;
                }
            }
        }
        if(!f)
            return false;
        for(int i=1;i<=tot;++i)
        {
            if(dis[e[i].v]>dis[e[i].u]+e[i].w)
                return true;
        }
        return false;
    }
};