HDU 2544 最短路【Dijkstra模板题】

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2544

思路：最短路的模板题

Dijkstra 算法是一种类似于贪心的算法，步骤如下：

1、当到一个点时，图上部分的点的最短距离已确定，部分点的最短距离未确定。

2、选一个所有未确定点中离源点最近的点，把它认为成最短距离。

3、再把这个点所有出边遍历一边，更新所有的点。

朴素算法（适用于稠密图复杂度 $N^2$ ）

#include<iostream>

#include<cstdio>

using namespace std;

const int maxn = 105;

const int INF = 9999999;

int w[maxn][maxn];

int dis[maxn];

bool vis[maxn];

int n, m;

void dijkstra()

{

    for(int i = 1; i <= n; i++)

        vis[i] = false;

    for(int i = 1; i <= n; i++)

        dis[i] = (i == 1 ? 0 : INF);

    for(int i = 1; i <= n; i++)

    {

        int x, m = INF;

        for(int y = 1; y <= n; y++)

        {

            if(!vis[y] && dis[y] <= m)

                m = dis[x = y];

        }

        vis[x] = true;

        for(int y = 1; y <= n; y++)

        {

            dis[y] = min(dis[y], dis[x] + w[x][y]);

        }

    }

}

int main()

{

    while(scanf("%d%d", &n, &m) != EOF)

    {

        if(n == m && n == 0)

            break;

        else

        {

            for(int i = 1; i <= n; i++)

                for(int j = 1; j <= n; j++)

                    w[i][j] = INF;

            for(int i = 1; i <= m; i++)

            {

                int a, b, c;

                scanf("%d%d%d", &a, &b, &c);

                w[a][b] = c;

                w[b][a] = c;

            }

        }

        dijkstra();

        cout << dis[n] << endl;

    }

}

优先队列优化（适用于稀疏图复杂度E*log(V)）

#include<iostream>

#include<queue>

using namespace std;

const int maxn = 2e5 + 10;

const int INF = 0x3f3f3f3f;

struct heapnode

{

    int d;

    int u;

    //结构体内嵌函数，速度较快

    bool operator <(const heapnode &a) const

    {

        return d > a.d;

    }

};

struct node

{

    int to;

    int cost;

    int next;

};

node edges[maxn << 1];

int head[maxn];

int d[maxn];

bool vis[maxn];

int n, m;

int tot;

void add_edges(int u, int v, int cost)

{

    edges[++tot].to = v;

    edges[tot].cost = cost;

    edges[tot].next = head[u];

    head[u] = tot;

}

void dijkstra()

{

    priority_queue<heapnode>q;

    for(int i = 1; i <= n; i++)

        d[i] = INF, vis[i] = 0;

    d[1] = 0;

    q.push((heapnode)

    {

        0, 1

    });

    while(!q.empty())

    {

        heapnode x = q.top();// 每次取出d值最小的点

        q.pop();

        int u = x.u;

        if(vis[u])

            continue;

        vis[u] = 1;

        for(int i = head[u]; i; i = edges[i].next)

        {

            node v = edges[i];

            if(d[v.to] > d[u] + v.cost)

            {

                d[v.to] = d[u] + v.cost;

                q.push((heapnode)

                {

                    d[v.to], v.to

                });

            }

        }

    }

}

int main()

{

    while(scanf("%d %d", &n, &m) != EOF)

    {

        if(n == m && n == 0)

            break;

        else

        {

            tot = 0;

            for(int i = 1; i <= n; i++)

                head[i] = 0;

            for(int i = 1; i <= m; i++)

            {

                int a, b, c;

                scanf("%d%d%d", &a, &b, &c);

                add_edges(a, b, c);

                add_edges(b, a, c);

            }

            dijkstra();

            cout << d[n] << endl;

        }

    }

}

巴特西

HDU 2544 最短路【Dijkstra模板题】

最新文章

热门文章

巴特西

HDU 2544 最短路 【Dijkstra模板题】

最新文章

热门文章

HDU 2544 最短路【Dijkstra模板题】