手写堆TLE
查看原帖
手写堆TLE
651883
hwh_qwq楼主2025/6/22 11:30

请问我的堆是哪里有问题嘛?还是说这题想要不超时只能用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;
}
2025/6/22 11:30
加载中...