美文网首页ACM - ICPC
最短路径模板

最短路径模板

作者: JesHrz | 来源:发表于2018-07-27 16:09 被阅读9次

    堆优化的Dijkstra

    typedef pair<int, int> P;   //first为边的权值,second为点的编号
    const int N = 100005;
    int dis[N];
    vector<P>e[N];  //first为点的编号, second为边的权值
    priority_queue<P, vector<P>, greater<P> >q;
    void dij(int s)
    {
        for (int i = 1; i <= N; ++i)    dis[i] = 0xffffff;
        dis[s] = 0;
        while (!q.empty())  q.pop();
        q.push(P(0, s));
        while (!q.empty())
        {
            P c = q.top(); q.pop();
            if (dis[c.second] < c.first)
                continue;
            for (int i = 0; i < e[c.second].size(); ++i)
            {
                int v = e[c.second][i].first;
                int w = e[c.second][i].second;
                if (dis[v] > c.first + w)
                {
                    dis[v] = c.first + w;
                    q.push(P(dis[v], v));
                }
            }
        }
    }
    

    普通Dijkstra

    const int N = 5005;
    bool book[N];
    int dis[N];
    int e[N][N];    //e最开始要初始化为0xffffff,e[i][i]设为0
    void dij(int s)
    {
        book[s] = true;
        for (int i = 1; i <= N; ++i)
            dis[i] = e[s][i];
        for (int i = 1; i < N; i++)
        {
            int u, min = 0xffffff;
            for (int j = 1; j <= n; j++)
                if (!book[j] && min > dis[j])
                {
                    min = dis[j];
                    u = j;
                }
            book[u] = 1;
            for (int v = 1; v <= n; v++)
                if (e[u][v] != 0xffffff && dis[v] > dis[u] + e[u][v])
                    dis[v] = dis[u] + e[u][v];
        }
    }
    

    SPFA

    const int M = 250005;
    const int N = 100005;
    struct edge
    {
        int to, next, w;
    }e[M << 1];
    int cnt, head[N]
    bool vis[N];
    void spfa(int s, long long d[])
    {
        for (int i = 0; i < n; ++i) d[i] = 0xfffffff;
        memset(vis, false, sizeof(vis));
        queue<int>q;
        d[s] = 0;
        vis[s] = true;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            vis[u] = false;
            for (int i = head[u]; i; i = e[i].next)
            {
                int v = e[i].to;
                int w = e[i].w;
                if (d[v] <= d[u] + w)   continue;
                d[v] = d[u] + w;
                if (!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }

    相关文章

      网友评论

        本文标题:最短路径模板

        本文链接:https://www.haomeiwen.com/subject/ocdgmftx.html