Jimmy1112 @ 2022-05-14 10:56:38
下面是我的代码,dijkstra+堆优化:
cpp
#include<bits/stdc++.h>
#define rg register int
using namespace std;
int n,m,h[100011],sum=0,l=0,dis[100011],st,d;
bool bj[100011];
struct node
{
int to,nxt,s;
}a[400011];
struct nood
{
int zz,w;
}b[100011];
inline void add(int x,int y,int z)
{
sum++;
a[sum].to=y;
a[sum].nxt=h[x];
a[sum].s=z;
h[x]=sum;
}
inline void put(int x,int y)
{
int net,now;
l++;
b[l].zz=x;
b[l].w=y;
now=l;
while(now>1)
{
net=now/2;
if(b[net].zz>=b[now].zz) return ;
swap(b[net],b[now]);
now=net;
}
}
inline nood get()
{
int net,now=1;
nood k=b[1];
b[1]=b[l--];
while(now*2<=l)
{
net=now*2;
if(net<l&&b[net].zz<b[net+1].zz) net++;
if(b[now].zz>=b[net].zz) break;
swap(b[now],b[net]);
now=net;
}
return k;
}
int main()
{
scanf("%d%d%d",&n,&m,&st);
for(rg i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dis[st]=0;
d=h[st];
bj[st]=1;
do
{
dis[a[d].to]=a[d].s;
put(a[d].s,a[d].to);
d=a[d].nxt;
}
while(d!=0);
for(rg i=1;i<n;i++)
{
nood q=get();
bj[q.w]=1;
d=h[q.w];
do
{
if(dis[a[d].to]>q.zz+a[d].s) dis[a[d].to]=q.zz+a[d].s;
d=a[d].nxt;
}
while(d!=0);
}
for(rg i=1;i<=n;i++)
{
printf("%d ",dis[i]);
}
return 0;
}
by a746 @ 2022-07-07 09:39:53
试试每个数组都翻个20倍大小?我设数据点上限+4会RE三个点
以及这是有向图应该不需要存两条边吧
by Jimmy1112 @ 2022-07-07 20:01:28
@a746 3Q!