代码：
#include<iostream> #include<vector> #include<cstdio> #include<queue> #include<map> #include<cstdlib> #include<cmath> #include<algorithm> #include<set> #include<cstring> using namespace std; typedef long long ll; const ll INF=2147483647; const int MM=500002; const int NM=10002; int n,m,s;//点,边,起始 int dis[NM];//最小距离 bool book[NM];//记录有没有作为顶点搜索过 //链式向前星 struct NODE{ int to; int nxt; int c; }node[MM];//链式向前星 int head[NM],lcnt=1; void add(int a,int b,int c){ node[lcnt].to=b; node[lcnt].c=c; node[lcnt].nxt=head[a]; head[a]=lcnt++; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>s; for(int i=1;i<=n;i++){ dis[i]=INF; } for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; //if(a==b) // continue; add(a,b,c); //add(b,a,c); } for(int i=head[s];i;i=node[i].nxt){ //从起始点开始枚举 int idx=node[i].to; dis[idx]=min(node[i].c,dis[idx]); //更新最短路 } dis[s]=0; //自身距离为0 book[s]=1; //标记搜索过 for(int kkk=1;kkk<n;kkk++){ //枚举每个点(用编号) int minn=INF,u=0; for(int i=1;i<=n;i++){ if(!book[i]&&dis[i]<minn){ u=i; //枚举每个已经被标记了但是没有被搜索过的点 minn=dis[i]; //找距离最小的 } } /*for(int i=1;i<=n;i++){ if(mp[u][i]<INF){ dis[i]=min(dis[i],dis[u]+mp[u][i]); } }*/ for(int i=head[u];i;i=node[i].nxt){ int idx=node[i].to; //正在搜索的点开始,枚举每一条边 dis[idx]=min(dis[idx],dis[u]+node[i].c); //更新最短距离,设f[i][j]为i到j的最大距离,d[i]为起始点到i的距离 //得到 d[j]=min(d[j],d[i]+f[i][j]) } book[u]=1; //标记这个点搜索过了 } for(int i=1;i<=n;i++){ cout<<dis[i]<<" "; } return 0; }
1.储存方式：
链式向前星>> https://www.cnblogs.com/dudujerry/p/9915713.html
int n,m,s;//点,边,起始
int dis[NM];//最小距离
bool book[NM];//记录有没有作为顶点搜索过
//链式向前星
struct NODE{
int to;
int nxt;
int c;
}node[MM];//链式向前星
int head[NM],lcnt=1;
void add(int a,int b,int c){
node[lcnt].to=b;
node[lcnt].c=c;
node[lcnt].nxt=head[a];
head[a]=lcnt++;
}
2.更新所有与根节点连接的最短路
for(int i=head[s];i;i=node[i].nxt){ //枚举所有与起点连接的边
int idx=node[i].to;
dis[idx]=min(node[i].c,dis[idx]); //更新最短路
}
dis[s]=0; //自身距离为0
book[s]=1; //标记搜索过
使用book记录是否作为过用来更新的点， 则搜完之后 book[s]=1
3.接下来枚举除源点外所有点来作为用来更新最短路的点
依 ”从上次求出最短路的点中选出最短路最小的点“ 的顺序遍历除源点以外的n-1个点
for(int kkk=1;kkk<n;kkk++){ //枚举n-1次，因为原点已经被用来更新过了
int minn=INF,u=0;
for(int i=1;i<=n;i++){
if(!book[i]&&dis[i]<minn){ //枚举每个已经被标记了但是没有被搜索过的点
u=i;
minn=dis[i]; //找距离最小的
}
}
. . .
4.从选出的点开始更新所有与它连接的边
设已知 源点到i点的距离dis[i] 和 点i到点j的距离f[i][j] (未知当前dis [ j ]是否正确）
可以得到 dis [ j ] = min ( dis [ j ] , dis [ i ] + f [ i ] [ j ] )
根据上面的方程可以遍历所有与选出的点，算出最短路
. . .
for(int i=head[u];i;i=node[i].nxt){ int idx=node[i].to; //正在搜索的点开始,枚举每一条边 dis[idx]=min(dis[idx],dis[u]+node[i].c); //更新最短距离,设f[i][j]为i到j的最大距离,d[i]为起始点到i的距离 //得到 d[j]=min(d[j],d[i]+f[i][j]) } book[u]=1; //标记这个点搜索过了 }
5.输出
dis [ i ]就是源点到i点的距离
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}