代码求查错
#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;
}
谢谢大家(●ˇ∀ˇ●)