求助,Dijkstra+邻接表+手写堆,WA了8个点
查看原帖
求助,Dijkstra+邻接表+手写堆,WA了8个点
222101
wxwyx楼主2020/8/15 13:02

代码求查错

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> node;
vector<node> a[10005];
node heap[500005];
int size=0;
int n,m,s,INF=2147483647;
int dis[10005],v[10005];
void push(node x)
{
	size++;
	heap[size]=x;
	int now=size;
	while(now/2>0)
	{
		if(heap[now].second<heap[now/2].second)
			swap(heap[now],heap[now/2]);
		else return ;
		now/=2;
	}
}
void hdelete()
{
	heap[1]=heap[size];
	size--;
	int now=1;
	while(now*2<=size)
	{
		int r=now*2;
		if(heap[r].second>heap[r+1].second)
			r++;
		if(heap[r].second<heap[now].second)
			swap(heap[now],heap[r]);
		else return;
		now=r;
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		a[x].push_back(node(y,z));
	}
	for(int i=1;i<=n;i++)
		dis[i]=INF;
	dis[s]=0;
	push(node(s,0));
	while(size>=1)
	{
		node t=heap[1];
		hdelete();
//		cout<<t.second<<endl;
		int next=t.first;
		if(v[next]) continue;
		v[next]=1;
		for(int i=0;i!=a[next].size();i++)
		{
			if(!v[a[next][i].first]&&dis[a[next][i].first]>dis[next]+a[next][i].second)
			{
				dis[a[next][i].first]=dis[next]+a[next][i].second;
				push(a[next][i]);
			}
			
		}
	}
	for(int i=1;i<=n;i++)
		cout<<dis[i]<<" ";
	cout<<endl;
	return 0;
}

谢谢大家(●ˇ∀ˇ●)

2020/8/15 13:02
加载中...