差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:namespace:广度优先搜索_bfs_与标数最短路_dijkstra [2020/05/18 17:51]
great_designer
+++ 2020-2021:teams:namespace:广度优先搜索_bfs_与标数最短路_dijkstra [2020/05/18 18:05] (当前版本)
great_designer
@@ 行 1: / 行 1: @@
-写在前面：为什么把这两个页面合二为一了呢？因为只需要把最短路中的优先队列换成普通的队列，就变成了广度优先搜索。
+写在前面：我们总共有三门课讲到最短路：数据结构、离散II、算法。
+（推荐任韩图论，一本跨越了数竞和计竞的高中数竞书）
+为什么把这两个页面合二为一了呢？
+只需要把最短路中的优先队列换成普通的队列，就变成了广度优先搜索。也就是说，如果所有的边权都为1，priority_queue也可以用queue替代。
+另外还要注意，Dijkstra的实质，是将给定的源点生成最短路“场”，一下子求了**一定范围内所有点的最短路**。有的题目会用到这个场的性质。
 =====Dijkstra的三步走=====
@@ 行 109: / 行 117: @@
 </hidden>
-我们看到，只有新权重（节点+权重）比老权重小的时候，才编号，其余时候并不编号。编号完了，就把这个刚编的节点压入堆。
+只有新权重（节点+权重）比老权重小的时候，才编号，其余时候并不编号。编号完了，就把这个刚编的节点压入堆。
-注意！这里的堆，默认是大顶堆，而我们每次取的时候（见第二步），要取最小的元素。
+注意！这里的堆，默认是大顶堆，而每次取的时候（见第二步），要取最小的元素。
-因此每次压入的时候，将每个权重（第一元素）取负，变相将大顶堆改造成小顶堆。这个操作很巧妙。
+因此**每次压入的时候，将每个权重（第一元素）取负**，变相将大顶堆**改造成小顶堆**。这个操作很巧妙。
 总共只有这三个步骤。后面没有了。
+====完整代码====
+<hidden click here if you want to know more>
+<code c++>
+void Dijkstra(int begin)
+{
+    //步骤一
+    memset(dis,0x3f,sizeof(dis));
+    memset(vis,0,sizeof(vis));
+    q.push(make_pair(0,begin));
+    dis[begin]=0;
+    //步骤二
+    while(!q.empty())
+    {
+        int x=q.top().second;
+        q.pop();
+        if(vis[x])
+        {
+            continue;
+        }
+        vis[x]=1;
+        //步骤三
+        int i;
+        for(i=0;i<top[x];i++)
+        {
+            int y=V[x][i].first;
+            int time=V[x][i].second;
+            if(dis[y]>dis[x]+time)
+            {
+                dis[y]=dis[x]+time;
+                q.push(make_pair(-dis[y],y));
+            }
+        }
+    }
+}
+</code>
+</hidden>
 =====利用队列的BFS非递归实现=====
@@ 行 125: / 行 175: @@
 void bfs(int v)//以v开始做广度优先搜索（非递归实现，借助队列）
 {
+    //步骤一
     list<int>::iterator it;
     visited[v] = true;
@@ 行 130: / 行 181: @@
     queue<int> myque;
     myque.push(v);
+    //步骤二
     while (!myque.empty())
     {
         v = myque.front();
         myque.pop();
+        //步骤三
         for (it = graph[v].begin(); it != graph[v].end(); it++)
         {
@@ 行 150: / 行 203: @@
 </hidden>
+=====例题=====
+给出了一个具有n个顶点和m条边的加权连通无向图。你知道有人在顶点1点燃了火，它会立即将当前位置烧成灰尘，并以每秒1英里的速度扩展到相邻的地方。火将在顶点处分裂到所有未点亮的边上，并在至少两个火在同一点相遇时引发爆炸。革命者喜欢爆炸。他们想让你数一数图表上发生的爆炸次数。
+第一行包含整数n，m（1≤n≤3×105，0≤m≤106）-顶点数。
+接下来的m行中的每一行包含3个整数ui，vi，wi（1≤ui，vi≤n，1≤wi≤9）-第i条边的端点和第i条边的权重。
+保证图是连通的。
+图可以包含自循环和多条边。示例1显示了处理它们的方法。
+输入文件的大小可能很大。请不要读得太慢。
+输出将在图形上以单行方式发生的爆炸数。
+====样例====
+输入
+3
+1 1
+2 1
+2 1
+输出
+输入
+5
+2 1
+3 1
+3 1
+4 1
+4 1
+输出
+====题解====
+在点上爆炸意味着存在至少两个点可以是他最短路上的前驱；在边上爆炸意味着这条边不在最短路里。因此求出最短路即可。
+边权≤ 9 并不意味着可以使用SPFA。本题的本意是使用O(nw) 的桶排序Dijkstra, 但是由于vector实现的桶排Dijkstra 和邻接表+ priority_queue 实现的O(mlogm) Dijkstra 速度在使用输入随机数生成器的方法开大数据后没法拉开差距，因此为了避免卡常数都放了过去。
+总之大概的意思是，这东西恰好是最短图标记图后直接算出来。
+<hidden click here if you want to know more>
+<code C++>
+#include<stdio.h>
+#include<string.h>
+#include<queue>
+using namespace std;
+struct node
+{
+	int to,next,val;
+};
+struct node e[10000050];
+int head[1000005],cnt,n,m,K;
+void add(int first,int second,int z)
+{
+	e[cnt]=(struct node){second,head[first],z};
+	head[first]=cnt++;
+}
+priority_queue<pair<int,int> > q;
+int dis[1000005],vis[1000005],ans,used[1000005];
+void Dijkstra()
+{
+	q.push(make_pair(0,1));
+	memset(dis,0x3f,sizeof(dis));
+	dis[1]=0;
+	while(!q.empty())
+	{
+		int first = q.top().second;
+		q.pop();
+		if(vis[first])
+		{
+			continue;
+		}
+		vis[first] = 1;
+		int i;
+		for(i=head[first];i!=-1;i=e[i].next)
+		{
+			int to1 = e[i].to;
+			if(dis[to1]>dis[first]+e[i].val)
+			{
+				dis[to1]=dis[first]+e[i].val;
+				used[to1]=1;
+				q.push(make_pair(-dis[to1],to1));
+			}
+			else if(dis[to1]==dis[first]+e[i].val)
+			{
+				used[to1]++;
+			}
+		}
+	}
+}
+int main()
+{
+	scanf("%d%d",&n,&m);
+	memset(head,-1,sizeof(head));
+	int i,x,y,z;
+	for(i=1;i<=m;i++)
+	{
+		scanf("%d%d%d",&x,&y,&z);
+		add(x,y,z);
+		add(y,x,z);
+	}
+	Dijkstra();
+	for(i=1;i<=n;i++)
+	{
+		if(used[i]>=2)
+		{
+			used[i]--;
+		}
+		m-=used[i];
+	}
+	printf("%d\n",m);
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具