第一步

定义数组和变量：

int f[101][101]; //将得到的数据转化成邻接矩阵
int ans[101];  //用来记录答案（从1到各点的最短路径）
int q1[105],l=0,r=1;  //队列，详见https://blog.csdn.net/a_n_d_y_s_u_n__/article/details/119543473
bool YN[101];  //记录一个点是否入队

然后初始化：

for(re int i=1;i<=n;++i){
		YN[i]=false;
		for(re int j=1;j<=n;++j){
			if(i!=j)
			    f[i][j]=MAXint;
			else
			    f[i][j]=0;    
		}
	}

第二步

假设我们得到了一个这样子的图和数据

点数：6
边数：9
每条边相连的点以及边的权值：

1 2 7  //意思是：点1和点2之间有一条线，权值为7
1 3 9
1 6 14
2 4 15
2 3 10
3 6 2
3 4 11
6 5 9
4 5 6

将得到的点数，边数，每条边相连的点以及边的权值存下来

    re int n,m;
	cin>>n>>m;
    re int a,b,q;
	for(re int i=1;i<=m;++i){
		cin>>a>>b>>q;
		f[a][b]=f[b][a]=q;
	}

第三步

经过初始化，读入后，我们就要开始分析计算方法了，首先，写出一个表格

F	1	2	3	4	5	6
1	0	7	9	∞	∞	14
2	7	0	10	15	∞	∞
3	9	10	0	11	∞	2
4	∞	15	11	0	6	∞
5	∞	∞	∞	6	0	9
6	14	∞	2	∞	9	0

因为我们是求每个点到1的最短距离，所以我们把ans的值赋为f[1][i]
代码：

for(re int i=1;i<=n;++i)
	    ans[i]=f[1][i];

接着我们来分析一下解题方法

首先让1进队q1[r]=1,++r;并且把YN[i]赋值为true表示已经进过队列了，防止重复进队，重复搜索。

然后从1开始搜索，搜索到所有与1相连并且没有进过队列的点，可以得到分别是2,3,6，然后依次将他们推进队列，然后队列里是这样的：

1(队头)	2	3	6(队尾)

接着将YN[2,3,6]都设置为true

现在，到了最重要的部分了，如何计算这个点到1的最短路？

我们知道，是求最短路，所以先拿出min函数，因为ans数组里已经在初始化时有了部分数据，所以我们也要和原来在ans数组里的数与现在这个数到下一个数的距离+这个数到1的距离比较，把ans赋值为两者之间最小的一个（可能有点难听懂，你也可以直接跳过往下看举例）

举例：

如何求1到5的最短路？

我们可以从1开始搜索，1可以到达2,3,6，ans是这样的：

1	2	3	4	5	6
0	7	9	∞	∞	14

然后把1退出队列，搜索2

2可以到达3,4（因为YN[1]的值已经为true了，所以不算进去），我们把4推进队列，2到3的距离为10，到4的距离是15，于是我们重新计算1到3,4的最小值，目前知道以下两个路线：

到3
- 1—>3 距离为ans[3]=9（也就是1到3的距离）
  - 1—>2—>3 距离为ans[2]+f[2][3]=7+10=17（也就是1到2的距离+2到3的距离）

比较两个距离大小，9<17，所以将ans[3]赋值为9

到4
- 1—>4 距离为ans[4]=∞（也就是1到4的距离）
  - 1—>2—>4 距离为ans[2]+f[2][4]=7+15=22（也就是1到2的距离+2到4的距离）

比较两个距离大小，22<∞，所以将ans[4]赋值为22

于是经过这一波计算，ans数字变成了这样

1	2	3	4	5	6
0	7	9	22	∞	14

然后把2推出队列，搜索3

队列就成了这样

| 3 | 6 |4|
|--|--|--|

3可以到达4,6，距离分别是11和2，目前知道以下两个路线：

到4
- 1—>4 距离为ans[4]=22（也就是1到4的距离）
  - 1—>3—>4 距离为ans[3]+f[3][4]=9+11=20（也就是1到3的距离+3到4的距离）

比较两个距离大小，20<22，所以将ans[4]赋值为20

到6
- 1—>6 距离为ans[6]=14（也就是1到6的距离）
  - 1—>3—>6 距离为ans[3]+f[3][6]=9+2=11（也就是1到3的距离+3到6的距离）
    -
    比较两个距离大小，11<14，所以将ans[6]赋值为11

1	2	3	4	5	6
0	7	9	20	∞	11

以此类推，经过重复计算，我们可以得到1到每个点的最短路了

程序：

while(l<=r){
		re int now=q1[l];
		for(re int i=1;i<=n;++i){
			if(f[now][i]!=MAXint&&f[now][i]!=0){
				if(YN[i]==false) q1[r]=i,++r,YN[i]=true;
				ans[i]=min(ans[i],f[now][i]+ans[now]);
			}
		} 
		++l;
	}

第四步

输出答案

for(re int i=1;i<=n;++i){
		cout<<ans[i]<<" "; 
	}

总结：

程序：

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("abm,avx,avx2,mmx,popcnt,sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define in inline
#define re register
using namespace std;
int f[101][101];
int ans[101];
int q1[105],l=0,r=1;
bool YN[101];
const int MAXint=2147483647;
int main(){
	re int n,m;
	cin>>n>>m;
	for(re int i=1;i<=n;++i){
		YN[i]=false;
		for(re int j=1;j<=n;++j){
			if(i!=j)
			    f[i][j]=MAXint;
			else
			    f[i][j]=0;    
		}
	} 
    re int a,b,q;
	for(re int i=1;i<=m;++i){
		cin>>a>>b>>q;
		f[a][b]=f[b][a]=q;
	}
	q1[r]=1,++r;
	YN[1]=true;
	for(re int i=1;i<=n;++i)
	    ans[i]=f[1][i];
	while(l<=r){
		re int now=q1[l];
		for(re int i=1;i<=n;++i){
			if(f[now][i]!=MAXint&&f[now][i]!=0){
				if(YN[i]==false) q1[r]=i,++r,YN[i]=true;
				ans[i]=min(ans[i],f[now][i]+ans[now]);
			}
		} 
		++l;
	} 
	for(re int i=1;i<=n;++i){
		cout<<ans[i]<<" "; 
	}
}

本文作者：Andysun06

F	1	2	3	4	5	6
1	0	7	9	∞	∞	14
2	7	0	10	15	∞	∞
3	9	10	0	11	∞	2
4	∞	15	11	0	6	∞
5	∞	∞	∞	6	0	9
6	14	∞	2	∞	9	0

F	1	2	3	4	5	6
1	0	7	9	∞	∞	14
2	7	0	10	15	∞	∞
3	9	10	0	11	∞	2
4	∞	15	11	0	6	∞
5	∞	∞	∞	6	0	9
6	14	∞	2	∞	9	0

F	1	2	3	4	5	6
1	0	7	9	∞	∞	14
2	7	0	10	15	∞	∞
3	9	10	0	11	∞	2
4	∞	15	11	0	6	∞
5	∞	∞	∞	6	0	9
6	14	∞	2	∞	9	0