4.11力扣的开端

好家伙,强制要求要刷力扣哎呀!!

不写不知道,一写下一跳和我之前用的平台完全不一样,写的是奇奇怪怪的,看题解看了半天(看格式)

不管了,慢慢的适应吧,也许这就是代码的最规范的书写

学长今天讲了图

我对prim算法以及迪杰斯特拉,的印象有些模糊了

所以在这继续复习复习一下

prim算法是求最小生成树的

在我的理解就是,直接生成树,把一个一个的点拉入树内,每次拉的点都是离树最近的进树

进入树内就打上标记,且要遍历一遍以这个点更新一遍离树的最短距离

最后点都进入了树就完成了

#include<stdio.h>
int map[5010];//记录是否用过。
int dis[5010];
int max=1999999;
int maps[5010][5010];//记录边距的数组如maps[1][3]=3表示点一到点3的距离为3
long long sum;
long long min;
int hh=0;
int next;//新加入树的点
void beg(int a){
for(int hg=1;hg<=a;hg++)
{for(int jk=1;jk<=a;jk++){maps[hg][jk]=max;maps[jk][hg]=max;}
}}int main(){
int n,m;//点和边的数量
int a,b,c;//输入的数据
int jl;//就是一个用于循环的变量scanf("%d%d",&n,&m);
beg(n);for(int h=1;h<=m;h++){scanf("%d%d%d",&a,&b,&c);if(c<maps[a][b]){maps[a][b]=c;maps[b][a]=c;}
}for(int lp=1;lp<=n;lp++)
dis[lp]=maps[1][lp];//1默认为起点map[1]=1;//起点为用过的
for(int i=1;i<n;i++){min=max;for(jl=1;jl<=n;jl++){if(dis[jl]<min&&map[jl]==0){min=dis[jl];next=jl;}}if(min==max){printf("orz");hh++;break;}map[next]=1;sum=sum+dis[next];//加上最短的路程for(int hj=1;hj<=n;hj++)//对每个点到树的最小的距离进行更新{if(map[hj]==0&&maps[next][hj]<dis[hj]&&i<n-1)//i<n-1最后一次就不用更新了{dis[hj]=maps[next][hj];}}}
if(hh==0)
printf("%lld",sum);return 0;
}

很典型的求最小生成树

也可以把条件改改

变成求最大的也是ok的 

印象直接加深了呀

ok接下来是迪杰斯特拉算法

和floyed基本的原理是一样的,dp思想了,但是不需要遍历一边1到n只求s一个点到其他点的最短距离,求得东西变少了,时间复杂度也变成了o(n2)了,但是代码复杂了许多.

首先用邻间矩阵存边,不联通的就是无穷(边可以有向也可以无向    区别就是改几行代码的事)

开一个p数组是打标记数组,ans数组就是答案数组

初始化时ans[n]=a[s][n];就是那s点到n点的距离直接放进去(只是初始化)

然后把s点自己在p数组内打上标记t[s]=0自己到自己的距离就是0

随后遍历一遍t数组取距离最小的且为打上标记的为next,p[next]上标记,

以next为中间点遍历(p数组标记的就不要遍历了),要是t[n]>t[next]+a[next][s]就更新为t[next]+a[next][s]

经过,n-1的遍历全部的点都打上了标记,就结束了

此时的t[]数组在不断的遍历下变成了s点到其他点的最短距离了

#include<stdio.h>
int map[1001000]={0};//为0的就是T标号
long long dis[1001000];
long long max=2147483647;void bg(int u){//赋初值函数
for(int h=1;h<=u;h++){dis[h]=max;
}
}struct node{
int to;
int chang;
int next;//上一条是边数据的下标}nodes[1001000];long long min(long long jl,long long jk){if(jl<jk){return jl;
}
else{return jk;
}}int cin;//表示结构体数组的下标（就是一个一个数组的用无实际的意义）int first[1001000]={0};//保存头的数组（下标就是头！）值的含义是在结构体中保存的边对应的下标
//值表示以这个头开始的最后一条线void add(int a,int b,int c){
cin++;//用新的来存
nodes[cin].to=b;//to表示到那去（边的终点）
nodes[cin].chang=c;//chang表示边的长度
nodes[cin].next=first[a];//next表示找到上一以a为起点的上以条边的数组的下标
first[a]=cin;//现在a到b变成了以a为起点的最后一条边就改一下first[a]的值（这个值是储存这条边的数组的下标）}int main()
{
int n,m,k;
int jj,kk,ll;
scanf("%d%d%d",&n,&m,&k);
bg(n);
for(int j=1;j<=m;j++){scanf("%d%d%d",&jj,&kk,&ll);add(jj,kk,ll);}
dis[k]=0;
int pos=k;
while(map[pos]==0){map[pos]=1;for(int i=first[pos];i!=0;i=nodes[i].next){if(map[nodes[i].to]==0){dis[nodes[i].to]=min(dis[nodes[i].to],dis[pos]+nodes[i].chang);}}long long mine=max;for(int y=1;y<=n;y++){if(dis[y]<mine&&map[y]==0){mine=dis[y];pos=y;}}}for(int y=1;y<=n;y++){printf("%lld ",dis[y]);
}return 0;
}

翻自己的代码,没找到用邻间矩阵存边就找了用链式前向星的代码(一定是当时写的题目对空间卡的紧了) ,没有关系,顺便复习一下链式前向星.

ok

写力扣就不写在这了,全是最基础的题目,等两天我习惯了力扣的代码书写,顺便学一点c++的语法来开荒力扣

bbb

撒花谢幕!!!!!