Dijkstra

2019-11-14 10:47:45

字体：大中小

来源：转载

供稿：网友

不得不说C++自带的Heap忒好使（P党跪哭，撒花~~~）。看完这篇博文后，一直坚信SPFA大发好的窝决定怒转Dijkstra……有兴趣的童鞋们可以看一下http://blog.csdn.net/xiazdong/article/details/8193680 这里写图片描述结论： so 临时敲了个板子……

#include <cstdio>#include <algorithm>#include <queue>#define INF 2147483647#define maxn 10000+5#define maxm 500000+5using namespace std;int vis[maxn],x,y,z,n,m,s,head[maxn],id,d[maxn];struct xx{ int v,next,q;}b[maxm];struct yy{ int u,d; bool Operator < (const yy& a)const{ return d>a.d; }};void add(int u,int v,int q){ b[++id]=(xx){v,head[u],q}; head[u]=id;}void Dijkstra(int s){ for (int i=1;i<=n;i++) d[i]=INF,vis[i]=0; d[s]=0; PRiority_queue <yy> q; q.push((yy){s,0}); while (!q.empty()) { yy x=q.top();q.pop(); if (!vis[x.u]) { vis[x.u]=1; for (int k=head[x.u];k!=0;k=b[k].next) if (d[b[k].v]>d[x.u]+b[k].q) { d[b[k].v]=d[x.u]+b[k].q; q.push((yy){b[k].v,d[b[k].v]}); } } }}int main(){ scanf("%d%d%d",&n,&m,&s); for (int i=0;i<m;i++) scanf("%d%d%d",&x,&y,&z); add(x,y,z); Dijkstra(s); for (int i=1;i<=n;i++)printf("%d ",d[i]); return 0;}

上一篇：JAVA中int、String的类型转换

下一篇：1021.Deepest Root (25)