蒟蒻求助：zkw线段树dijkstra只有70分

代码如下:```cpp #include #define INF 0x7fffffff #define min(a,b) a.val<b.val?a:b using namespace std; struct Edge{ int to,next,cost; }edge[1048576]; struct node{ int ind,val; }dis[32768]; int n,m,s,head[10007],cnt,bit,ans[10007]; bool vis[10007]; inline void build(){ for(bit=1;bit<=n+1;bit<<=1); for(register int i=bit+1;i<=bit+n;++i){ dis[i].ind=i-bit; } for(register int i=bit<<1;i>=1;--i){ dis[i].val=INF; } } inline void update(int ind,int val){ dis[bit+ind].val=val; for(register int i=(bit+ind)>>1;i;i>>=1){ dis[i]=min(dis[i<<1],dis[i<<1|1]); } } inline void add(int u,int v,int w){ edge[++cnt].next=head[u]; edge[cnt].cost=w; edge[cnt].to=v; head[u]=cnt; } int main(){ scanf("%d%d%d",&n,&m,&s); for(register int i=1;i<=n;++i){ ans[i]=INF; } build(); ans[s]=0; for(register int i=1;i<=m;++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); if(u==v){ continue; } add(u,v,w); if(u==s){ ans[v]=w; update(v,w); } } while(dis[1].val<INF){ int u=dis[1].ind; vis[u]=true; update(u,INF); for(register int i=head[u];i;i=edge[i].next){ register int v=edge[i].to; register int w=edge[i].cost; if(ans[u]+w<ans[v]&&!vis[v]){ ans[v]=ans[u]+w; update(v,ans[v]); } } } for(register int i=1;i<=n;++i){ printf("%d ",ans[i]); } return 0; }