不得不說(shuō)C++自帶的Heap忒好使（P黨跪哭，撒花~~~）。 看完這篇博文后，一直堅(jiān)信SPFA大發(fā)好的窩決定怒轉(zhuǎn)Dijkstra……有興趣的童鞋們可以看一下http://blog.csdn.net/xiazdong/article/details/8193680 結(jié)論： so 臨時(shí)敲了個(gè)板子……
#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;}
結(jié)論： 
so 臨時(shí)敲了個(gè)板子……
