【dijkstra】迪杰斯特拉算法
洛谷P1828 香甜的黄油 例题讲解
算法介绍
-
Dijkstra算法是一种用于解决图论中最短路径问题的贪心算法。它由荷兰计算机科学家艾兹格·迪克斯特拉(Edsger Dijkstra)于1956年首次提出,主要用于寻找有向加权无环图(如果有负环,则不能用dijkstra算法,建议spfa)中从起点到其他所有顶点的最短路径。该算法通过迭代的方式更新每个节点的最短距离,直到找到目标节点或遍历完整个图。
算法工作原理如下:
- 初始化:标记源节点的距离为0,其余节点距离为无穷大;将源节点加入待处理集合(通常称为“优先队列”)。
- 选择最小距离节点:从未处理集合中取出当前距离最小的节点,并将其从集合中移除。
- 更新邻接节点:对于该节点的所有邻居,如果经过该节点到达它们的距离小于之前的估计值,就更新其距离并将它们加入待处理集合。 重复步骤2和3,直到处理完所有节点或者找到目标节点。
例题演示
[USACO3.2] 香甜的黄油 Sweet Butter
题目描述
Farmer John 发现了做出全威斯康辛州最甜的黄油的方法:糖。
把糖放在一片牧场上,他知道 N N N 只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。
Farmer John 很狡猾。像以前的 Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。
Farmer John 知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)。
输入格式
第一行包含三个整数 N , P , C N,P,C N,P,C,分别表示奶牛数、牧场数和牧场间道路数。
第二行到第 N + 1 N+1 N+1 行,每行一个整数,其中第 i i i 行的整数表示第 i − 1 i-1 i−1 头奶牛所在的牧场号。
第 N + 2 N+2 N+2 行到第 N + C + 1 N+C+1 N+C+1 行,每行包含三个整数 A , B , D A,B,D A,B,D,表示牧场号为 A A A 和 B B B 的两个牧场之间有一条长度为 D D D 的双向道路相连。
输出格式
输出一行一个整数,表示奶牛必须行走的最小的距离和。
样例输入 #1
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
样例输出 #1
8
提示
数据范围
对于所有数据, 1 ≤ N ≤ 500 1 \le N \le 500 1≤N≤500, 2 ≤ P ≤ 800 2 \le P \le 800 2≤P≤800, 1 ≤ A , B ≤ P 1 \le A,B \le P 1≤A,B≤P, 1 ≤ C ≤ 1450 1 \le C \le 1450 1≤C≤1450, 1 ≤ D ≤ 255 1 \le D \le 255 1≤D≤255。
样例解释
作图如下:
P2
P1 @--1--@ C1|| 5 7 3| | C3C2 @--5--@P3 P4
把糖放在4号牧场最优。
代码与讲解
- 此题题型十分经典,类似于“医院设置”这题,都是一个图,每个结点带上一个权值,在每一个结点取一个位置,计算出整个图的一个值的和,可以说是经典一类题。之前在【DFS】 洛谷P1364 医院设置里面也有讲过😊,如果看这题有点费力,可以先去看一看那题,相信看完之后再回到这题会豁然开朗。
- 具体步骤
- 储存所有的奶牛对应的牧场号,并读入牧场的平面图
- 从每一个牧场结点开始,算法搜索并计算求和,将每一次的结果存在minn里面
- 写dijsktra代码,注意含参
#include<bits/stdc++.h>
#define fi first
#define PII pair<int,int>//定义整型对
#define pb push_back
#define se second
#define int long long
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)//加快输入输出
using namespace std;
const int N = 1e4;
int n,p,c,arr[N];
int dis[N],minn = 1e9,sum;
bool vis[N];
vector <PII> v[N];
map <int,int> mp;void dijkstra(int A)//含参的dijsktra函数
{priority_queue <PII,vector<PII>,greater<PII>> q;//开含整型对的优先队列,并从小到大排序for(int i = 1;i <= p;i++)//将每个结点到原点的初始距离设成无穷大(以便后期比较大小刷新),每个点标记为0{dis[i] = 1e9;vis[i] = 0;}q.push({0,A});//将距离放在队列参数的第一个,以便于优先队列的自动字典序排列dis[A] = 0;//初始距离为0while(q.size()){auto t = q.top();//拿出队头q.pop();//弹出来int now = t.se;//取出队头的第二个参数:点if(vis[now]) continue;//当这个点用过了就直接跳过vis[now] = 1;//标记这个点,表示已经用过for(auto tt:v[now])//搜索邻接结点{int spot = tt.fi,w = tt.se;//拿出结点的两个参数(点,边权)if(dis[spot] > dis[now] + w)//当此时点到原点的距离没有将要更新的更小时{dis[spot] = dis[now] + w;//更新q.push({dis[spot],spot});//压入队列}}}
}signed main()
{IOS;//加快输入输出cin>>n>>p>>c;for(int i = 1;i <= n;i++)//重复奶牛个数次{int a;cin>>a;mp[a]++;//用map来存储每一个奶牛}for(int i = 1;i <= c;i++)//重复边条数次{int a,b,c;cin>>a>>b>>c;v[a].pb({b,c});//建边,最后一个参数是权值v[b].pb({a,c});//双向边}for(int i = 1;i <= p;i++)//重复牧场(图的结点)个数次{sum = 0;//求和初始为0dijkstra(i);//在每一个点开始算for(int j = 1;j <= p;j++) sum += dis[j]*mp[j];//将图上每一个奶牛与距离的积求和minn = min(minn,sum);//存进minn变量,同时保证闽南、始终是最小的那一个}cout<<minn;//输出
}
总结
- dijkstra算法对于初学者来说还是有一点小复杂的,主要因为它涉及到优先队列的自动排序问题,但耐下心来,一步步模拟,感受算法的过程,多写一写代码,慢慢的就会感觉到也不是那么复杂。迪杰斯特拉是一种很巧妙且快捷的算法,在各个方面的都有跟大的作用😎