弱化版全过,标准版全错,求解

P4779 【模板】单源最短路径(标准版)

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

@时间重洗 好了,就是那个原因【笑哭】 谢谢大佬


|