迪杰斯特拉模板,用STL的堆来优化。
——————————————————————
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<iostream> #include<cstdio> #include<queue> using namespace std; int n,m,S,tot,Next[500010],head[20000],tree[500010],val[500010]; bool visit[20000]; long long dis[20000]; struct node { int u,dis; }t; struct cmp { bool operator()(node a,node b) { return a.dis>b.dis; } }; priority_queue<node,vector<node>,cmp> Q; void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } int main() { scanf("%d%d%d",&n,&m,&S); tot=0; for (int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if (x==y) continue; add(x,y,z); } for (int i=1;i<=n;i++) { visit[i]=false; dis[i]=2147483647; } t.u=S;t.dis=0; dis[S]=0; Q.push(t); while (!Q.empty()) { t=Q.top(); Q.pop(); int u=t.u; if (visit[u]) continue; visit[u]=true; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (!visit[v]&&dis[v]>dis[u]+(long long)val[i]) { dis[v]=dis[u]+val[i]; t.u=v;t.dis=dis[u]+val[i]; Q.push(t); } } } for (int i=1;i<=n-1;i++) printf("%lld ",dis[i]); printf("%lld\n",dis[n]); return 0; } |