`

【最短路/3大模板】总结【2012-1-22新增前插的spfa】

阅读更多



首先献上模板:【点都是默认为从1到n编号,用dijk和floyd时要注意重边】
①DIJK
#define inf 0x3fffffff
#define M 105

int dist[M], map[M][M], n;
bool mark[M];

void init ()
{
	int i, j;
	for (i = 1; i <= n; i++)    //i==j的时候也可以初始化为0,只是有时候不合适
		for (j = 1; j <= n; j++)
			map[i][j] = inf;
}

void dijk (int u)
{
	int i, j, mins, v;
	for (i = 1; i <= n; i++)
	{
		dist[i] = map[u][i];
		mark[i] = false;
	}
	mark[u] = true;
	dist[u] = 0;    //既然上面的map当i==j时不是0,就要这句
	while (1)
	{
		mins = inf;
		for (j = 1; j <= n; j++)
			if (!mark[j] && dist[j] < mins)
				mins = dist[j], v = j;
		if (mins == inf)
			break;
		mark[v] = true;
		for (j = 1; j <= n; j++)
			if (!mark[j] && dist[v] + map[v][j] < dist[j])
				dist[j] = dist[v] + map[v][j];
	}
}

②Floyd
#define inf 0x3fffffff	//注意,太大会溢出
#define M				//最大点数
int n, dist[M][M];           //n:实际点数

void init ()			//有时候需要初始化
{
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = i + 1; j <= n; j++)
            dist[i][j] = dist[j][i] = inf;
}

void floyd ()
{
    int i, j, k;
    for (k = 1; k <= n; k++)
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)    //有的题目会溢出就要自己变通了
                if (dist[i][k] + dist[k][j] < dist[i][j])
	                    dist[i][j] = dist[i][k] + dist[k][j];
}

③vector后插的SPFA
#define inf 0x3fffffff
#define M 105    //最大点数
struct son{
    int v, w;
};
vector<son> g[M];
bool inq[M];       //入队列标记
int dist[M], n;    //n:实际点数

void init ()
{
	for (int i = 1; i <= n; i++)
		g[i].clear();
}

void spfa (int u)
{
    int i, v, w;
    for (i = 1; i <= n; i++)
    {
        dist[i] = inf;
        inq[i] = false;
    }
    queue<int> q;
    q.push (u);
    inq[u] = true;
    dist[u] = 0;
    while (!q.empty())
    {
        u = q.front();
        q.pop();
        inq[u] = false;
        for (i = 0; i < g[u].size(); i++)
        {
            v = g[u][i].v;
            w = g[u][i].w;
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                if (!inq[v])
                {
                    q.push (v);
                    inq[v] = true;
                }
            }
        }
    }
}

④模拟前插的SPFA(多数情况下比③快,数据较为复杂就会看出来)
#define inf 0x3fffffff
#define M 1005	//最大点数

struct edge{
    int v, w, next;
}e[10005];		//估计好有多少条边

int pre[M], cnt, dist[M], n;
bool inq[M];
//注意初始化
void init ()
{
    cnt = 0;
    memset (pre, -1, sizeof(pre));
}
//注意双向加边 
void addedge (int u, int v, int w)    //加边函数,慢慢模拟就会明白的
{
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = pre[u];		//接替已有边
    pre[u] = cnt++;				//自己前插成为u派生的第一条边
}

void spfa (int u)
{
    int v, w, i;
    for (i = 1; i <= n; i++)	//对于从1到n的编号
        dist[i] = inf, inq[i] = false;
    dist[u] = 0;
    queue<int> q;
    q.push (u);
    inq[u] = true;
    while (!q.empty())
    {
        u = q.front();
        q.pop();
        inq[u] = false;
        for (i = pre[u]; i != -1; i = e[i].next)
        {
            w = e[i].w;
            v = e[i].v;
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                if (!inq[v])
                {
                    q.push (v);
                    inq[v] = true;
                }
            }
        }
    }
}


第一题:http://acm.hdu.edu.cn/showproblem.php?pid=2544
灰常水,floyd、dijk、spfa都可以

第二题:http://acm.hdu.edu.cn/showproblem.php?pid=2066
简单题,多源多终点,spfa、dijk都很快解决

第三题:http://acm.hdu.edu.cn/showproblem.php?pid=2112
用STL的map把地名映射到编号就可以套模板了,注意路是双向的就行了

第四题:http://acm.hdu.edu.cn/showproblem.php?pid=1874
和第一题一样的水

第五题:http://acm.hdu.edu.cn/showproblem.php?pid=1142
最短路+记忆化搜索
详情:http://972169909-qq-com.iteye.com/blog/1149589


第六题:http://acm.hdu.edu.cn/showproblem.php?pid=1385
floyd记忆路径
详情:http://972169909-qq-com.iteye.com/blog/1150803

第七题:http://acm.hdu.edu.cn/showproblem.php?pid=1548
水题,构图后直接dijk或spfa就可以了

第八题:http://acm.hdu.edu.cn/showproblem.php?pid=1217
floyd的灵活运用
详情:http://972169909-qq-com.iteye.com/blog/1149095

第九题:http://acm.hdu.edu.cn/showproblem.php?pid=2680
简单题,多起点单终点,反过来dijk或者spfa就可以了,注意路是单向的,所有路都要反过来,逆向思维

第十题:http://acm.hdu.edu.cn/showproblem.php?pid=2923
题目意思可能比较难懂,而且有重边,floyd
详情:http://972169909-qq-com.iteye.com/blog/1150818

第十一题:http://acm.hdu.edu.cn/showproblem.php?pid=2962
直接枚举或二分枚举+最短路
详情:http://972169909-qq-com.iteye.com/blog/1159652

第十二题:http://acm.hdu.edu.cn/showproblem.php?pid=2722
这题主要是构图麻烦,会用sscanf就比较好做了,构好图之后就是水题了

第十三题:http://acm.hdu.edu.cn/showproblem.php?pid=1690
暴力构图,枚举2点间距离,根据表格定好花费,然后直接floyd就可以了【注意数太大要用64位,无穷大定为-1比较好处理】

第十四题表示压力好大……

第十五题:http://acm.hdu.edu.cn/showproblem.php?pid=1596
floyd水题

第十六题:http://acm.hdu.edu.cn/showproblem.php?pid=1598
并查集+贪心 或 二分枚举+最短路
详情:http://972169909-qq-com.iteye.com/blog/1159593

第十七题表示不想做……

第十八题:http://acm.hdu.edu.cn/showproblem.php?pid=2363
枚举高度差+最短路,比较容易错
详情:http://972169909-qq-com.iteye.com/blog/1159650

第十九题表示很蛋疼……

第二十题:http://acm.hdu.edu.cn/showproblem.php?pid=2833
一题比较难的记忆化搜索+最短路【或dp+最短路】
详情:http://972169909-qq-com.iteye.com/blog/1159661




3
2
分享到:
评论

相关推荐

    ACM/ICPC模板

    --SPFA(最短路快速算法) // thanks to love8909 几何相关 --初等几何学 --多边形几何 --几种凸包算法 --半平面交算法 --旋转卡壳算法 数据结构 --可合并堆(左偏树实现) --树状数组 --Trie树 //thanks to love8909 ...

    最短路的Floyd-Dijkstra-Spfa板子

    做ACM最短路问题普遍算法的Floyd-Dijkstra-Spfa板子..

    最短路SPFA

    1. **初始化**:设置起点到所有顶点的距离为无穷大,起点到自身的距离为0。创建一个队列,将起点加入队列,并标记起点为已入队状态。 2. **循环处理队列中的顶点**: - 取出队列头部的顶点。 - 对于该顶点的所有...

    有向图的spfa模板

    spfa模板,双向图的,但是里面也有介绍改成单向图的。 实际是freepascal的,但是没有分类,只好放到C/C++分类里了,希望能帮到大家

    ACM图论模板合集.pdf

    图论--最短路--第K短路(IDA*)(IDA Star)模板 传递闭包: 传递闭包 欧拉与哈密尔顿路径: 欧拉回路 图论--欧拉回路--弗罗莱算法模板 LCA: 图论--LCA--Tarjan(离线) 图论--LCA--树上...

    SPFA算法模板

    ### SPFA算法详解 #### 一、算法简介 SPFA(Shortest Path Faster Algorithm)算法是一种高效的单源最短路径算法。它由西南交通大学的段凡丁教授在1994年提出。与传统的最短路径算法如Dijkstra算法相比,SPFA在...

    最短路模板(详细注解)

    同时,对于这些经典算法的变种和扩展,如Floyd-Warshall算法(用于求所有节点对之间的最短路径)和Johnson's Algorithm(处理大规模负权图的最短路问题),也要有所了解,以便在面对更复杂问题时能灵活应对。...

    图论- 最短路- Bellman-Ford 算法与 SPFA.rar

    1. 初始化:将源点的所有路径长度设为0,其他顶点的路径长度设为无穷大。 2. 迭代:对图中的每一条边进行V-1次松弛操作(V为图中顶点的数量)。每次迭代中,如果找到一条更短的路径,就更新目标顶点的路径长度。 3. ...

    图论,ACM SPFA 和Bellman_ford.ppt 最短路算法

    总结来说,SPFA算法是求解带负权边图的最短路径的一种高效方法,虽然在最坏情况下可能不如Bellman-Ford算法稳定,但通常在实践中表现出更好的性能。理解这两种算法的原理和实现细节对于解决图论问题和参加编程竞赛都...

    cpp代码-SPFA模板

    3. **初始化**:开始时,将源点的距离设置为0,其他所有顶点的距离设置为无穷大,表示未发现的路径。 4. **核心循环**:进入主循环,每次从队列中取出一个顶点`u`,遍历与其相邻的所有顶点`v`,如果通过边`(u, v)`...

    队列优化的Bellmanford最短路算法(SPFA)C++实现

    队列优化的Bellman-Ford最短路算法(SPFA,Shortest Path Faster Algorithm)是一种在图论中用于寻找有向图中单源最短路径的算法,它是在经典Bellman-Ford算法基础上进行优化得到的。Bellman-Ford算法本身能够处理...

    SPFA.cpp SPFA算法

    最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。

    最短路课件(链式前向星+堆优化+SPFA)

    最短路算法进阶(链式前向星+堆优化+SPFA) 本文主要介绍了最短路算法的进阶知识,包括链式前向星、堆优化和SPFA算法的应用。 一、链式前向星 链式前向星是一种存图方式,用于存储有向图中的边信息。这种存图方式...

    STL实现的容易理解的二位spfa模板

    STL实现的,看完了一定会懂了的。我就是看的这个呢亲

    SPFA.rar_SPFA

    在提供的"最短路之SPFA算法.mht"文件中,很可能包含了关于SPFA算法的具体实现、例子以及分析。这个文件可能包含了用编程语言(如C++、Python等)实现的SPFA算法代码,以及通过实例来解释如何运用该算法求解最短路径...

    SPFA算法优化及应用

    SPFA(Shortest Path Faster Algorithm)是一种高效的单源最短路算法,广泛应用于图论和动态规划等领域。下面是对SPFA算法的详细介绍和优化。 基本实现 SPFA算法的基本思想是通过relax操作来更新节点的距离值。...

    SPFA算法.doc

    SPFA(Shortest Path Faster Algorithm)算法是一种用于解决图论中的单源最短路径问题的算法,它是贝尔曼-福特(Bellman-Ford)算法的一种优化版本,主要应用于求解带有负权重边的图的最短路径。SPFA通过使用队列...

    最短路全家桶(Floyd,Dijkstra,SPFA)

    相比于Bellman-Ford算法,SPFA在实践中通常更快,但其最坏情况下的时间复杂度仍为O(n^2)。SPFA对于稀疏图,即边的数量远小于节点数量的情况,表现良好。 链式前向星存图是一种常用的图存储结构,它使用邻接表而非...

    spfa.rar_SPFA

    1. 初始化:设置所有顶点到源点的距离为无穷大(除了源点自身距离为0),并将源点加入队列。 2. 循环处理:当队列不为空时,执行以下操作: - 取出队首元素u,遍历u的所有邻接点v。 - 计算新路径d' = d[u] + w(u,...

    SPFA.zip_SPFA

    标题中的"SPFA.zip_SPFA"表明这是一个与SPFA算法相关的压缩文件,SPFA全称为Shortest Path Faster Algorithm,即最短路径更快算法。这是一种解决图论中的单源最短路径问题的算法,通常用于有向图。描述提到SPFA算法...

Global site tag (gtag.js) - Google Analytics