蒟蒻求助！！

DYhzx_QWQ @ 2022-10-13 19:47:36

#include<bits/stdc++.h>
using namespace std;
int dis[10005],n,m,q,bj[10005];
struct bb {
    int tot,son[1001],w[1001];
}hzx[10001];
struct bl {
    int dis,x;
    bool operator < (bl k) const {
        return dis<k.dis;
    }
};
priority_queue<bl> mp;
void dij(int x) {
    mp.push(bl{dis[x],x});
    while(!mp.empty()) {
        bl tmp=mp.top();
        mp.pop();
        if(bj[tmp.x]) continue;
        bj[tmp.x]=1;
        for(int i=1;i<=hzx[tmp.x].tot;i++) {
            int u=hzx[tmp.x].son[i];
            if(dis[u]>dis[tmp.x]+hzx[tmp.x].w[i]) {
                dis[u]=dis[tmp.x]+hzx[tmp.x].w[i];
                if(bj[x]==0) {
                    mp.push(bl{dis[u],tmp.x});
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) {
        dis[i]=INT_MAX;
    }
    for(int i=1;i<=m;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        int u=++hzx[x].tot;
        hzx[x].son[u]=y,hzx[x].w[u]=z;
        u=++hzx[y].tot;
        hzx[y].son[u]=x,hzx[y].w[u]=z;
    }
    dis[q]=0;
    dij(q);
    for(int i=1;i<=n;i++) {
        cout<<dis[i]<<' ';
    }
    return 0;
}

by vdfes @ 2022-10-13 19:57:45

第一眼数组开小

by DYhzx_QWQ @ 2022-10-13 19:59:43

开大了，WA了

by vdfes @ 2022-10-13 20:12:17

建议学习链式前向星

by DYhzx_QWQ @ 2022-10-13 20:12:33

emm...

by DYhzx_QWQ @ 2022-10-13 20:13:18

就是不想学习链式前向星才打的这个lj东西

by binbin_200811 @ 2022-10-13 20:14:08

建议·学习链式前向星及vector

by DYhzx_QWQ @ 2022-10-13 20:18:01

刑，OK

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dis[200005],n,m,q,bj[200005];
vector<ll> hzxson[200002];
vector<ll> hzxw[200002];
struct bl {
    ll dis,x;
    bool operator < (bl k) const {
        return dis>k.dis;
    }
};
priority_queue<bl> mp;
void dij(ll x) {
    mp.push(bl{dis[x],x});
    while(!mp.empty()) {
        bl tmp=mp.top();
        mp.pop();
        if(bj[tmp.x]) continue;
        bj[tmp.x]=1;
        int l=hzxson[tmp.x].size();
        for(ll i=0;i<l;i++) {
            ll u=hzxson[tmp.x][i];
            if(dis[u]>dis[tmp.x]+hzxw[tmp.x][i]) {
                dis[u]=dis[tmp.x]+hzxw[tmp.x][i];
                mp.push(bl{dis[u],u});
            }
        }
    }
}
int main(){
    cin>>n>>m>>q;
    for(ll i=1;i<=n;i++) {
        dis[i]=INT_MAX;
    }
    for(ll i=1;i<=m;i++) {
        ll x,y,z;
        cin>>x>>y>>z;
        hzxson[x].push_back(y),hzxw[x].push_back(z);
        hzxson[y].push_back(x),hzxw[y].push_back(z);
    }
    dis[q]=0;
    dij(q);
    for(ll i=1;i<=n;i++) {
        cout<<dis[i]<<' ';
    }
    return 0;
}

by DYhzx_QWQ @ 2022-10-13 20:27:33

我看成无向图了....