52pts 求调

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

wedngda @ 2024-08-30 04:01:25

由于本人不会重载运算符所以手写了一个巨丑而且常数巨大的堆,然而这不是重点,重点是只过了一半另一半WA
还有一个问题,就是开了O2之后会全部MLE,不开还能跑,不知道为什么

#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define INF 1000000001
int n,m,s;
int head[N<<1],nxt[N<<2],to[N<<2],w[N<<2],cnt=0;
int heap[N],id[N],point[N],sz=0;
void build()
{
    for(int i=1;i<=n;i++) heap[i]=INF,id[i]=i,point[i]=i;
    sz=n;
}
void swp(int x,int y)
{
    swap(heap[x],heap[y]);
    swap(point[id[x]],point[id[y]]);
    swap(id[x],id[y]);
}
void del(int k)
{
    int t=point[k];
    swp(t,sz);
    sz--;
    while((t<<1)<=sz)
    {
        if((t<<1)+1<=sz)
        {
            if(heap[t<<1]<heap[(t<<1)+1]) swp(t<<1,t),t<<=1;
            else swp((t<<1)+1,t),t=(t<<1)+1;
        }
        else if((t<<1)<=sz) swp(t<<1,t),t<<=1;
        else break;
    }
}
void add(int k,int val)
{
    heap[++sz]=val;
    id[sz]=k;
    point[k]=sz;
    int t=sz;
    while(t>>1>0)
    {
        if(heap[t>>1]>heap[t]) swp(t>>1,t),t>>=1;
        else break;
    }
}
void change(int k,int val)
{
    del(k);
    add(k,val);
}
int pop()
{
    int tmp=id[1];
    del(tmp);
    return tmp;
}
int make(int u,int v,int wi)
{
    nxt[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=wi;
    head[u]=cnt;
}
int main()
{
    cin>>n>>m>>s;
    build();
    int u,v,wi;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>wi;
        make(u,v,wi);
        make(v,u,wi);
    }
    int vis[N]={0},dis[N];
    for(int i=1;i<=n;i++) dis[i]=INF;
    int _cnt=n;
    dis[s]=0;
    change(s,0);
    pop();
    while(--_cnt)
    {
        vis[s]=1;
        for(int i=head[s];i!=0;i=nxt[i])
        {
            if(!vis[to[i]]&&dis[s]+w[i]<dis[to[i]]) dis[to[i]]=dis[s]+w[i],change(to[i],dis[to[i]]);
        }
        s=pop();
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
}

by st2010 @ 2024-08-30 04:17:36

你可以把输入改为scanf; 输出改为printf;


by st2010 @ 2024-08-30 04:19:08

可以减少时间


by st2010 @ 2024-08-30 04:34:05

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define int long long 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;

const int N = 1e5+10;
int n,m,T;
int A,B;
int dist[N],vis[N];
vector<PII>e[N];
void distra()
{
    priority_queue<PII,vector<PII>,greater<PII>>q;
    for(int i=1;i<=n;i++)  dist[i]=1e18;
    q.push({0,A});
    dist[A]=0;
    while(q.size())
    {
        auto t=q.top();q.pop();
        int now=t.se,dis=t.fi;
        if(vis[now]==1) continue;
        vis[now]=1;
        for(auto tt:e[now])
        {
            int spot=tt.se,w=tt.fi;
            if(dist[spot]>dist[now]+w)
            {
                dist[spot]=dist[now]+w;
                q.push({dist[spot],spot});
            }
        }
    }
}
signed main()
{
    IOS;
    cin>>n>>m>>A;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        e[a].pb({c,b});
    }
    distra();
    for(int i=1;i<=n;i++)
    cout<<dist[i]<<" ";
    return 0;
}

@wedngda


by wedngda @ 2024-08-30 12:43:48

@st2010 但是我时间上其实是可以过的,反而会MLE


by wedngda @ 2024-08-30 12:44:44

@st2010 STL看不懂orz


by st2010 @ 2024-08-30 12:57:55

@wedngda 你交一下看看


by wedngda @ 2024-08-30 13:18:51

@st2010 你的是AC的,我的开O2六个点全部MLE,不开#1 #2 #4WA


|