题目链接：

堆优化迪杰斯特拉，留着以后复习用

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int inf = 2147483647; 8 const int maxn = 500001; 9 struct Edge{10     int u,v,w;11 }e[maxn];12 struct Point{13     int na,s;14 }dis[maxn];15 struct cmp{16     bool operator ()(Point &a,Point &b){17         return a.s>b.s;18     }19 };20 priority_queue
          
           
            ,cmp> q;21 int m, n, sta;22 int head[maxn];23 bool vis[maxn];24 int main()25 {26 scanf("%d%d%d",&n,&m,&sta);//n 点 m 边 27 for(int i = 1; i <= m; i++)28 {29 int x,y,z;30 scanf("%d%d%d",&x,&y,&z);31 e[i].u = y;32 e[i].v = head[x];33 e[i].w = z;34 head[x] = i; 35 } 36 37 for(int i = 1; i <= n; i++)38 {39 dis[i].na = i;40 dis[i].s = inf;41 }42 43 dis[sta].s = 0;44 int now = 0;45 vis[0] = 1;46 q.push(dis[sta]);47 48 for(int k = 1; k < n; k++)49 {50 while(vis[now])51 {52 now = q.top().na;53 q.pop();54 }55 vis[now] = 1;56 int c = head[now];57 while(c)58 {59 int mu = e[c].u;60 if(dis[mu].s > dis[now].s+e[c].w)61 {62 dis[mu].s = dis[now].s+e[c].w;63 q.push(dis[mu]);64 }65 c = e[c].v; 66 }67 }68 for(int i = 1; i <= n; i++)69 printf("%d ",dis[i].s);70 return 0; 71 }