重庆网站seo教程,wordpress注册数字加字母随机数,网络推广都需要做什么,网络营销的销售方式迪杰斯特拉算法百度百科定义#xff1a;传送门 gh大佬博客#xff1a;传送门 迪杰斯特拉算法用来计算一个点到其他所有点的最短路径#xff0c;是一种时间复杂度相对比较优秀的算法 O#xff08;n2#xff09;#xff08;相对于Floyd算法来说#xff09; 是一种单源最短…迪杰斯特拉算法百度百科定义传送门 gh大佬博客传送门 迪杰斯特拉算法用来计算一个点到其他所有点的最短路径是一种时间复杂度相对比较优秀的算法 On2相对于Floyd算法来说 是一种单源最短路径算法但是它并不能处理负边权的情况 Dijkstra的算法思想①将一开始所有的非源点到源的距离设置成无限大你认为的无限大实际上是0x3f(int)或者0x7fffffff(long long)然后源到源距离设置成0不就是0吗然后每次找到一个距离源最短的点u将其变成白点枚举所有的蓝点如果源到白点存在中转站——一个蓝点使得源-蓝点和蓝点-白点的距离和更短就更新。②每找到一个白点就尝试更新其他蓝点直到更新完毕。 代码及注释 #includecstdio
#includeiostream
#includecstdlib
#includeiomanip
#includecmath
#includecstring
#includestring
#includealgorithm
#includetime.h
#includequeue
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pairint,int pr;
const double piacos(-1);
#define rep(i,a,n) for(int ia;in;i)
#define per(i,n,a) for(int in;ia;i--)
#define Rep(i,u) for(int ihead[u];i;iNext[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps1e-9;
ll pp1000000007;
ll mo(ll a,ll pp){if(a0 app)return a;a%pp;if(a0)app;return a;}
ll powmod(ll a,ll b,ll pp){ll ans1;for(;b;b1,amo(a*a,pp))if(b1)ansmo(ans*a,pp);return ans;}
ll read(){ll ans0;char last ,chgetchar();while(ch0 || ch9)lastch,chgetchar();while(ch0 ch9)ansans*10ch-0,chgetchar();if(last-)ans-ans;return ans;
}//快读
//headconst int maxn5001;
int g[maxn][maxn];//g数组用来存储图;
int n,m,s;//分别表示点的个数、有向边的个数、出发点的编号;
bool vis[maxn];//表示是否已经到达过;
int d[maxn];//d[i]表示从询问点到点i的最短路径;
const int inf2147483647;int main ()
{nread(),mread(),sread();rep(i,1,n){d[i]inf;rep(j,1,n)g[i][j]inf;g[i][i]0;//自己到自己的最短路径当然是0 }//初始化数组; rep(i,1,m){int uread(),vread(),wread();//u,v,i分别表示第i条有向边的出发点、目标点和长度;g[u][v]w;//读入; }vis[s]1;//将起点标记成已经到达;rep(i,1,n)d[i]g[s][i];//将最短路径初始化;//如果两点之间有路线就初始化为该距离如果没有就还是inf;while(1){int stt_node0,stt_disinf;//sttshortest 初始化两个变量 // stt_node表示最短路径的终点stt_dis表示最短路径的长度 rep(i,1,n){ if(vis[i]0d[i]stt_dis)//如果该点还没有到达并且他的距离小于最短距离 {stt_nodei,stt_disd[i];//更新变量 }}if(stt_node0) break;//如果已经没有可以更新的最短路径了就说明已经结束了vis[stt_node]1;//将该点标记成已经到达 rep(i,1,n){if(vis[i]||g[stt_node][i]inf)continue;//如果并没有到达或者是两点之间没有路径就进入下一层循环 d[i]min(d[i],stt_disg[stt_node][i]);//更新最短路径 }}rep(i,1,n)printf(%d ,d[i]);return 0;
} 我们考虑一下对它的优化。因为如果我们每一次都要扫一遍判断出边我们还不如直接存出边 邻接表链式前向星 #includecstdio
#includeiostream
#includecstdlib
#includeiomanip
#includecmath
#includecstring
#includestring
#includealgorithm
#includetime.h
#includequeue
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pairint,int pr;
const double piacos(-1);
#define rep(i,a,n) for(int ia;in;i)
#define per(i,n,a) for(int in;ia;i--)
#define Rep(i,u) for(int ihead[u];i;iNext[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps1e-9;
ll pp1000000007;
ll mo(ll a,ll pp){if(a0 app)return a;a%pp;if(a0)app;return a;}
ll powmod(ll a,ll b,ll pp){ll ans1;for(;b;b1,amo(a*a,pp))if(b1)ansmo(ans*a,pp);return ans;}
ll read(){ll ans0;char last ,chgetchar();while(ch0 || ch9)lastch,chgetchar();while(ch0 ch9)ansans*10ch-0,chgetchar();if(last-)ans-ans;return ans;
}//快读
//headconst ll INF 2147483647;
struct edge
{ll to, dis_, next;
} Edge[9999999];
struct node
{ll to, dis;inline friend bool operator(const node a, const node b){return a.dis b.dis;}
};
ll head[9999999], dis[9999999];
bool vst[9999999];
ll nodenum, edgenum, origin_node, cnt 1, t;
priority_queuenode q;inline void add_edge(ll from, ll to, ll value)
{Edge[cnt].to to;Edge[cnt].dis_ value;Edge[cnt].next head[from];head[from] cnt;
}inline void dijkstra()
{for (register int i 1; i origin_node; i){dis[i] INF;}//dis[origin_node]0;for (register int i origin_node 1; i nodenum; i){dis[i] INF;}q.push((node){origin_node, 0});while (!q.empty()){int x q.top().to;q.pop();if (vst[x])continue;vst[x] 1;for (register int i head[x]; i; i Edge[i].next){dis[Edge[i].to] min(dis[Edge[i].to], dis[x] Edge[i].dis_);q.push((node){Edge[i].to, dis[Edge[i].to]});}}
}int main()
{nodenum read(), edgenum read(), origin_node read() ;//tread();for (register int i 1; i edgenum; i){register int f, t, v;f read(), t read(), v read();add_edge(f, t, v);}dijkstra();rep(i,1,nodenum){printf(%lld ,dis[i]);}return 0;
} 转载于:https://www.cnblogs.com/lcezych/p/10739866.html
