讲了半天好像也许maybe听懂了一点，先写下来233
先整理整理怎么存（开始绕）
最简单的是邻接矩阵存，但是开到10000*10000就MLE了,所以我们用链式前向星存（据说是叫这个名字吧）
这是个什么鬼玩意呢？
我们在记录时，以输入的顺序记录。
我们记录一条边，就记下它的终点(to)，权值（就是边长）(dis)，以及和这条边的起点相同，编号稍微小一点的边的编号(next)（开始绕）
这里我们记录当前每个点的所有出边（就是起点是这个点的边）中编号最大的那一条边（因为上面的next是编号稍微小的边）
当然也可以依据自己的习惯存储边
先上段代码
int head[nmax],n,m,s;//head[i] 是 以 点 i 为 起 点 ， 所 有 出 边 中 编 号 最 大 的 一 个priority_queue q;void add(int fr,int _to,int _dis){cnt++; eage[cnt].to=_to; eage[cnt].dis=_dis; eage[cnt].next=head[fr];//fr 为 from 的 简 写 , 这 里 的 以 点 i 为 起 点 的 边 多 了 一 条， //所 以 上 一 个 以 点 i 为 起 点 的 编 号 最 大 的 边 就 是 这 里 的 以 i 为 起 点 编 号 最 大 的 边 的 上 一 条 边head[fr]=cnt; //更 新 head[i] }Edge [50001];const int inf=2147483647;int main(){ scanf("%d%d%d",&n,&m,&o_node);dis[o_node]=0;for(int i=1;i>from>>to>>dis; add(from,to,dis);}这一坨是存图
拿张图举个例子
假设我们输入边的数据如下(三个数n,m,s,n为起点，m为终点，s为边长)
1 2 2
2 3 2
1 3 5
2 4 1
3 4 2
1 4 4
那代码中的存储如下
Edge[1].to=2,Edge[1].dis=2,Edge[1].next=0,head[1]=1(这里指没有上一条边),head[1]=1(这里head[i]记录的是以i为起点，当前最大编号出边的编号)
Edge[2].to=3,Edge[2].dis=2,Edge[2].next=0,head[2]=2
Edge[3].to=3,Edge[3].dis=5,Edge[3].next=1,head[1]=3
.....................................
讲完存图，再来说这个算法是怎么实现的
要求最短路径，这里有点类似贪心。
首先选择一个距离起点最近的直达点b，记录当前点与b的距离，再由b进行相同的扩展，来更新起点与其它点的距离
这样更新了一圈后就是最短距离，
再举个栗子
没错还是刚才那张图，这里标出了每条边的权值
按照dijkstra算法，我们首先找到距离①最近的直达点②，由②更新出①到④的最短路为3，①到③的最短路为4，
那么程序怎么实现呢？
看注释吧
（代码from gh,注释自己加的）
#include #include #include using namespace std;const int INF = 2147483647;struct edge{int to, dis_, next;} Edge[500001];struct node{int to, dis;inline friend bool operator9)putnum(num/10);putchar('0'+num%10);}int main(){nodenum = getnum(), dgenum = getnum(),origin_node = getnum();for (register int i = 1; i >n>>m;for(int i=1;i>x>>y>>w;add(x,y,w);}memset(f,INF,sizeof(f));f[1]=0;vis[1]=1; int x=head[1];//手动模拟第一次出队while(x!=0){int y=a[x].pre;if(f[y]>a[x].w)f[y]=a[x].w;x=a[x].next;} int cnt=0;while(cnt='0'&&ch