detor @ 2022-07-15 11:51:54
全wr。
#include<bits/stdc++.h>
using namespace std;
struct pir{
short x,y;
}hp[500500];
int hs;
int h[100020],v[500020],w[500020],ne[500020],tot;
int mindis[100020];
int n,m,book[100020],k;
void add(int a,int b,int c){
v[tot]=b,w[tot]=c,ne[tot]=h[a];
h[a]=tot++;
}
void siftdown(int i)
{
if(i==0)return;
int t=i;
while(2*i<=hs)
{
if(hp[2*i].x<hp[t].x)
t=2*i;
if(2*i+1<=hs&&hp[2*i+1].x<hp[t].x)
t=2*i+1;
if(i!=t)
swap(hp[i],hp[t]);
else
return;
i=t;
}
return ;
}
void siftup(int i)
{
while(i>1)
{
if(hp[i].x<hp[i/2].x)
swap(hp[i],hp[i/2]);
else
return;
i/=2;
}
return;
}
int main(){
freopen("P4779_1.in","r",stdin);
freopen("P4779.out","w",stdout);
for(int i=1;i<=100010;i++){
mindis[i]=0x7fffffff;
}
memset(h,-1,sizeof h);
int a,b,c,t;
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
add(a,b,c);
}
// for(int i=h[1];~i;i=ne[i]){
// mindis[v[i]]=w[i];
// }
hp[1].x=0;
hp[1].y=k;
hs++;
mindis[k]=0;
while(hs){
t=hp[1].y;
hp[1]=hp[hs--];
siftdown(1);
if(book[t])continue;
book[t]=1;
for(int j=h[t];~j;j=ne[j]){
b=v[j];
if(book[b]==0&&mindis[b]>mindis[t]+w[j]){
mindis[b]=mindis[t]+w[j];
}
hs++;
hp[hs].x=mindis[b];
hp[hs].y=b;
siftup(hs);
}
}
for(int i=1;i<=n;i++){
cout<<mindis[i]<<' ';
}
return 0;
}
by detor @ 2022-07-15 11:52:28
文件输入多余的。忽略就行了。。
by 时间重洗 @ 2022-07-15 12:02:28
@detr 为什么要用short啊
by detor @ 2022-07-15 12:04:44
@时间重洗 一开始没看限制怕爆内存。 难道是这个?!我改改试试
by detor @ 2022-07-15 12:28:17
@时间重洗 好了,就是那个原因【笑哭】 谢谢大佬