请问我的堆是哪里有问题嘛?还是说这题想要不超时只能用stl里面的优先队列?
#include<iostream>
#include<vector>
using namespace std;
struct node{
int v,w;
};
vector<node> g[100005];
node mq[100005];
int n,m,s,tot,dis[100005];
bool vis[100005];
void insert(node s){
mq[++tot]=s;
int id=tot;
while(id!=1){
int fa=(id>>1);
if(mq[id].w>mq[fa].w){
swap(mq[id],mq[fa]);
id=fa;
}
else break;
}
return;
}
void mpop(){
mq[1]=mq[tot];
tot--;
int id=1;
while(id*2<=tot){
int ls=(id<<1),rs=(id<<1)|1;
if(rs>tot||mq[ls].w>mq[rs].w){
if(mq[ls].w>mq[id].w) swap(mq[ls],mq[id]);
else break;
id=ls;
}
else{
if(mq[rs].w>mq[id].w) swap(mq[rs],mq[id]);
else break;
id=rs;
}
}
}
int main(){
//freopen("P4779_1.in","r",stdin);
//freopen("hwh","w",stdout);
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
g[u].push_back((node){v,w});
}
for(int i=1;i<=n;i++){
dis[i]=2147483647;
}
dis[s]=0;
insert((node){s,0});
while(tot!=0){
int hwh=mq[1].v;
mpop();
for(int i=0;i<g[hwh].size();i++){
if(dis[hwh]+g[hwh][i].w<dis[g[hwh][i].v]){
dis[g[hwh][i].v]=dis[hwh]+g[hwh][i].w;
insert((node){g[hwh][i].v,dis[g[hwh][i].v]});
}
}
}
for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
return 0;
}