代码:
#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]<<" ";
}
转载于:https://www.cnblogs.com/dudujerry/p/9915505.html