专栏首页用户6093955的专栏【hdu 2544最短路】【Dijkstra算法模板题】

【hdu 2544最短路】【Dijkstra算法模板题】

Dijkstra算法

分析

Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路( Single-Source Shortest Paths, SSSP) , 即从单个源点出发, 到所有结点的最短路(这样最后返回你想要的那个节点对应的距离即可)。 该算法同时适用于有向图和无向图。 其伪代码如下:

清除所有点的标号
设d[0]=0, 其他d[i]=INF         //INF被定义为一个很大的数字
循环n次 {
在所有未标号结点中, 选出d值最小的结点x
给结点x标记
对于从x出发的所有边(x,y), 更新d[y] = min{d[y], d[x]+w(x,y)}        //w(x,y)是指边xy对应的权值
}

模板

可以根据上面的伪代码帮助理解

int Dijk()
{
    memset(vis, 0, sizeof(vis));
    memset(d, 0, sizeof(d));
    for(int i = 1; i <= N; i++)
        d[i] = ((i == 1) ? 0 : INF);        //注意这里INF一定要设置的很大         //这里的条件设置根据题意自行判断
    for(int i = 1; i <= N; i++)
    {
        int x, minn = INF;
        for(int j = 1; j <= N; j++)
        {
            if(!vis[j] && d[j] < minn)          //在所有未标号结点中, 选出d值最小的结点x
            {
                minn = d[j];
                x = j;
            }
        }
        vis[x] = 1;           //标记它
        for(int y = 1; y <= N; y++)
            d[y] = min(d[y], d[x] + route[x][y]);
    }
    return d[...];              //根据题意要求进行返回相应的值
}

以上内容参考自刘汝佳的《算法竞赛入门经典》

题目链接

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;
int N, M;
int a, b, c;
int route[maxn][maxn], d[maxn];
int vis[maxn];
int Dijk()
{
    memset(vis, 0, sizeof(vis));
    memset(d, 0, sizeof(d));
    for(int i = 1; i <= N; i++)
        d[i] = ((i == 1) ? 0 : INF);            //这里的条件设置根据题意自行判断
    for(int i = 1; i <= N; i++)
    {
        int x, minn = INF;
        for(int j = 1; j <= N; j++)
        {
            if(!vis[j] && d[j] < minn)          //在所有未标号结点中, 选出d值最小的结点x
            {
                minn = d[j];
                x = j;
            }
        }
        vis[x] = 1;           //标记它
        for(int y = 1; y <= N; y++)
            d[y] = min(d[y], d[x] + route[x][y]);
    }
    return d[N];
}
void init()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = i + 1; j <= N; j++)
            route[i][j] = route[j][i] = INF;
    }
}
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    while(cin >> N >> M && N && M)
    {
        init();
        for(int i = 0; i < M; i++)
        {
            cin >> a >> b >> c;
            route[a][b] = route[b][a] = c;
        }
        int minn = Dijk();
        cout << minn << endl;
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • 生成1~n的排列(模板),生成可重集的排列(对应紫书P184, P185)

    _DIY
  • 【Bit String Reordering UVALive - 6832 】【模拟】

    题目讲的主要是给你一个01串,然后给你要变成的01串格式,问你要转换成这一格式最少需要移动的步数。 题目不难,但当时并没有AC,3个小时的个人赛1道没AC,归...

    _DIY
  • HDU 6611 K Subsequence (最小费用最大流)

    用户2965768
  • POJ - 2195 Going Home 最小费用最大流

    题意:多组输入,n行m列矩阵包含相等个数的 ‘m’ 和 ‘ H ’ 每个men要到达Home,每移动一个格子耗费 1,求最小花费。

    用户2965768
  • 挑战程序竞赛系列(66):4.7字符串匹配(1)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • POJ 刷题系列:1753. Flip Game

    POJ 刷题系列:1753. Flip Game 传送门:POJ 1753. Filp Game 题意: 一个4*4的矩阵,每一格要么是白色,要么是黑色。现在...

    用户1147447
  • C++中动态申请数组

    动态申请一维数组 申请使用new,释放使用delete[] 可以通过数组名[下标]和*(数组名+下标)的方式访问数组

    卡尔曼和玻尔兹曼谁曼
  • BZOJ3295: [Cqoi2011]动态逆序对(cdq分治)

    对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删

    attack
  • BZOJ2754: [SCOI2012]喵星球上的点名(AC自动机)

    attack

扫码关注云+社区

领取腾讯云代金券