堆优化dijkstra（手写堆）

小根堆&＃xff1a;

struct Node{ll dist;int pos;bool operator>(const Node &x)const{//重载运算符,方便比较return dist>x.dist;}
}heap[maxm<<2];
int tot;
void ins1(Node x) {tot&＃43;&＃43;;heap[tot]&＃61;x;int i&＃61;tot;int j&＃61;i/2;while(j&&heap[j]>heap[i]) {swap(heap[j],heap[i]);i&＃61;j;j&＃61;i/2;}
}
Node pop1() {Node x&＃61;heap[1];heap[1]&＃61;heap[tot];tot--;int i&＃61;1;int j&＃61;i*2;if(j&＃43;1<&＃61;tot&&heap[j]>heap[j&＃43;1])j&＃43;&＃43;;while(j<&＃61;tot&&heap[i]>heap[j]){swap(heap[j],heap[i]);i&＃61;j;j&＃61;i*2;if(j&＃43;1<&＃61;tot&&heap[j]>heap[j&＃43;1])j&＃43;&＃43;;}return x;
}


dijkstra&＃xff1a;

#include
using namespace std;
#define ll long long
const int maxm&＃61;2e6&＃43;5;
int head[maxm],nt[maxm],to[maxm],w[maxm],cnt;
bool mark[maxm];
ll d[maxm];
int n,m,s;
//
struct Node{ll dist;int pos;bool operator>(const Node &x)const{return dist>x.dist;}
}heap[maxm<<2];
int tot;
void ins1(Node x) {tot&＃43;&＃43;;heap[tot]&＃61;x;int i&＃61;tot;int j&＃61;i/2;while(j>0&&heap[j]>heap[i]) {swap(heap[j],heap[i]);i&＃61;j;j&＃61;i/2;}
}
Node pop1() {Node x&＃61;heap[1];heap[1]&＃61;heap[tot];tot--;int i&＃61;1;int j&＃61;i*2;if(j&＃43;1<&＃61;tot&&heap[j]>heap[j&＃43;1])j&＃43;&＃43;;while(j<&＃61;tot&&heap[i]>heap[j]){swap(heap[j],heap[i]);i&＃61;j;j&＃61;i*2;if(j&＃43;1<&＃61;tot&&heap[j]>heap[j&＃43;1])j&＃43;&＃43;;}return x;
}
//
void add(int x,int y,int z){cnt&＃43;&＃43;;nt[cnt]&＃61;head[x];head[x]&＃61;cnt;to[cnt]&＃61;y;w[cnt]&＃61;z;
}
void dj(int st){ins1({0,st});for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)d[i]&＃61;1e18,mark[i]&＃61;0;d[st]&＃61;0;while(tot){int x&＃61;pop1().pos;if(mark[x])continue;mark[x]&＃61;1;for(int i&＃61;head[x];i;i&＃61;nt[i]){int v&＃61;to[i];if(d[v]>d[x]&＃43;w[i]){d[v]&＃61;d[x]&＃43;w[i];ins1({d[v],v});}}}
}
signed main(){scanf("%d%d%d",&n,&m,&s);for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}dj(s);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(d[i]&＃61;&＃61;1e18)d[i]&＃61;-1;printf("%lld\n",d[i]);}return 0;
}