作为前导知识的深度优先搜索和广度优先搜索就不赘述了，自行谷歌百度解决！（因为不是重点，大雾）
以下建图均使用链式前向星，默认有n个节点，m条边，关于链式前向星转之前的文章
下面贴一下标准建图以及输入！复习一下！
从洛谷上copy的
下面是链式前向星建图伪代码，仅作建图参考！（符合上述题意）
struct xing
{
int wei,quan,qian;
}bian[1010100];
int head[1100100],n,m,s,o1,o2,o3,cnt=0;
void add(int u,int v,int o3)
{
bian[++cnt].wei=v;
bian[cnt].quan=o3;
bian[cnt].qian=head[u];
head[u]=cnt;
}//链式前向星
cin>>n>>m>>s;//输入点数，边数，起点
while(m--){
cin>>o1>>o2>>o3;//输入边的信息
add(o1,o2,o3);//add函数加边
}
前置知识：贪心
在详细讲解DJI之前，首先介绍一下贪心思想，贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。其实按照字面意思就行了，就是贪吗QAQ
题源于洛谷
链接：https://www.luogu.com.cn/problem/P1181
显然，我们对于每一个正整数，不是把他自己单独开新的一段，就是把他并到他前面的段了，我们按照贪心的想法，能合并为什么不合并？当然要合并，这就是贪心，实在不能合并的在单列，这也就是所谓的贪婪，不去理会后面的情况，只做出现在最有利的选择，在这里也就是能合并就合并！
迪杰斯特拉（DJI）
好了，我们终于进入正题了，DJI的基本原理就是贪心，DJI的特点是首先建立一个集合，这个集合里面只有起点一个点，然后找除了集合里的点之外所有点中离起点最近的一个点，将他加入集合，并用新加入的点作为中转站，更新其他集合外的点到起点的距离，更新完之后再找一个除了集合里的点之外中离起点最近的点，再次中转更新，直到所有点都进入集合，这时候就获得了起点到其他点的最短距离！
光这么说可能还是难以理解，我们上个图，假设1为起点，现在集合里面只有1
建立一个len数组表示从起点到某点的已知最短距离，现在初始值分别为0 2 6 4
我们找了一下其他点，发现离1最近的点是2，很容易知道1和2的最短距离就是2，因为其他中转都一定比这个直接到达要长，所以2进入集合，现在集合里面有v1 v2两个点，然后以v2为中转，发现len3=6>len2+v2-v3=5；更新，这个过程专业上叫松弛，知道就行了，重要的是思想，len4<len2+v2-4;不更新，所以现在len数组的值为0 2 5 4；
下一步，现在集合外离v1最近的显然是v4，好，v4进入集合，以v4为中转，发现从v4中转到v3的距离是4+12>5,不更新len，在之后。。。v3就进集合了，好了，就此结束，得到len数组0 2 5 4，和Floyd结果一致！
显然在有n个节点的情况下，DJI的时间复杂度显然是n的二次方，还是比Floyd优秀很多，尽管他只能求单源最短路径
如果还不明白，不要紧，下面给出题目和伪代码，好好体会一下dji的思想
题目链接：https://www.luogu.com.cn/problem/P3371
memset(len,0x3f,sizof(len))//前面讲了，初始化len数组
len[s]=0;//自己到自己为0
bool used[101000];//用于判断某点是否已经进入集合
used[u]=1//起点自己开始就在里面
ans=0x3f3f3f3f//定义的极大值
for(int k=1;k<n;k++)//一共还有n-1个点要进集合
{
int u,ans=0x3f3f3f3f;//u和ans每次都得更新，因为都要找进入集合的新点
for(int i=1;i<n+1;i++)
if(!used[i]&&len[i]<ans){ans=len[i],u=i;}//如果不在集合中又比ans小，就把i点记录下来，遍历一遍后即可得所需进入集合的点
used[u]=1;//此时的u点进入集合
for(int i=head[u];i;i=bian[i].qian)//遍历与u点相连的点，当i=0的时候说明都遍历完了可以停了
{
int v=bian[i].wei;//与u点相连的v点
if(len[v]>len[u]+bian[i].quan)//如果可以松弛，其实这里多遍历了已经进入集合的点，集合的点是不会被松弛的，这里如果加一个判断跳过进入集合的点，会更快一些，但是不影响算法的正确性
len[v]=len[u]+bian[i].quan;//松弛更新
}
}
最后的len数组就是你要找的东西了！是不是大概知道DJI的本质了，就是贪心贪心贪心！
接下来讲的堆优化的dji也是因为贪心才能进行的，如果你不知道什么是堆，也不要紧，C++里面已经给您包装好了，我们管他叫优先队列，是按照一定优先级进行排序的一个队列，比如现在有1 2 3 4 8，现在要朝这个队列里面插入元素6，插入完就是1 2 3 4 6 8，始终保持一定的排序（当然是自定义的，我这个例子只是方便理解）
学过队列的人一定发现这好像和我学的队列不一样啊，废话，优先队列是用堆写的又不是用队列，当然不一样啊。你不懂就把他当成一个工具记住就行了（本菜鸡就是这么做的，有理想的人不建议这么做）！
有了优先队列，我们来找找DJI的不足之处，每次都要遍历一遍查询他是不是在集合里面，要全部对比一遍才能知道哪个点最短，这复杂度是o（n）了，属实弟弟啊，不就是从len数组里面每次找一个非集合内的最小值吗，如果我们能边更新边保持len的有序性，哦豁？成了，这不就是优先队列吗！
如果理解了DJI，我想你也能轻易理解接下来的代码，我会贴注释的嘻嘻
struct node{
int id,quan;//一个元素存贮点v和len[v]两个信息，也就是我写的id和quan
bool operator <(const node &a)const {
return quan>a.quan;//这是我为优先队列定义的优先级,len小的必然放到前面2333，当然你在有需求的时候也可以自己修改，由于优先队列不是重点，其他用法自行百度谷歌
}
};
for(int i=1;i<n+1;i++){
len[i]=INF;//初始化len，INF是个很大的值
}
len[s]=0;//自己到自己是0
priority_queue<node> q;//定义优先队列
q.push((node){s,0});//起点先进去
while(!q.empty())//只要队列不空
{
node u=q.top();//u就是优先队列队首，就是最小的那个
q.pop();//把u扔出去
if(used[u.id])continue;//如果你发现u这个点已经进队了，那么直接去队首再来一遍，因为进队说明u点已经在集合中了，不需要他当中转站了
used[u.id]=1;//标记进入集合
for(int i=head[u.id];i;i=bian[i].qian)//遍历边
{
int v=bian[i].wei;
if(len[v]>len[u.id]+bian[i].quan&&!used[v])//如果可以松弛并且没有在集合里面
{
len[v]=len[u.id]+bian[i].quan;//松弛
q.push((node){v,len[v]});//进队
}
}
}
这里我多说几句吧，为什么会出现重复进队的情况，假如有v1 v2 v3 v4四个点，v1是起点，v1和v2 v3都直接相连，假设v2先进队，那么v4铁定进队了，但是现在v1到v4还是比v1到v3长，所以v3当中转站，又因为v3到v4极短，所以v4又进队了，这时候队里就会有两个v4，但因为优先队列的特性，我们只取了一个最优。剩下的在队里的无用元素我们通过continue把他扔出去！
堆优化的DJI因为堆或者说优先队列的复杂度是log的，所以复杂度已经拿到了很优秀的nlogn。对于普通的Dji已经优化很多了
接着多说两句，虽然优化后的DJi很厉害，但是他也有不足之处，那就是负权值，因为其贪心的原理使其不能处理负权值，那是因为贪心这玩意是无法回溯的，他在后面发现了更短的路，但是他已经在集合了，不能更新了，所以无论是否优化的DJi只能处理正权图，举例子
v1 v2 v3，v1到v2有1权边，v1到v3有2权边，v3到v2有-2权编，很容易看出来len数组应该是0 0 2，但DJi处理出来却是0 1 2，看明白了吗，DJi先把v2给扔进集合了，后续也不更新人家，当然就炸裂了，有什么算法能处理负权边吗？当然有，下一篇就讲他，好了，到此为止吧，贴两个题
洛谷oj：https://www.luogu.com.cn/problem/P3371 普通DJi可过，Floyd不可过
洛谷oj：https://www.luogu.com.cn/problem/P4779 普通DJi，spfa不可过，堆优化的DJi可过
