求助，孩子WA飞了

MornHus @ 2023-01-07 22:37:34

#include<bits/stdc++.h>
#define maxn 100001
#define maxm 200001
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,u,v,w;
struct node{
    int to,val;
};
bool vis[maxn];
vector<node>gragh[maxn];
int dis[maxn];
struct point{
    int id,distance;
    bool operator < (const point &a)const{
        return distance<a.distance; 
    } 
};
priority_queue<point>q;
inline void dijkstra(){
    for(int i=1;i<=n;i++){
        if(i==s)continue;
        dis[i]=inf;
    }
    q.push({s,0});
    while(!q.empty()){
        point curr=q.top();q.pop();
        if(vis[curr.id])continue;
        vis[curr.id]=1;
        for(int i=0;i<gragh[curr.id].size();i++){
            if(dis[gragh[curr.id][i].to]>dis[curr.id]+gragh[curr.id][i].val){
                dis[gragh[curr.id][i].to]=dis[curr.id]+gragh[curr.id][i].val;
                q.push({gragh[curr.id][i].to,dis[gragh[curr.id][i].to]});
            }
        }
    }
}
int main(){
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&u,&v,&w);
        gragh[u].push_back({v,w});
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by Ruiqun2009 @ 2023-01-07 23:13:26

我的写法：（拿到 P8814 全站最优解的快读快写、手写 32 位 bitset（其实可以改成压 64 位）、手写小根堆、vector 存图、dijkstra+堆优化）

#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <utility>
#include <stdexcept>
#include <queue>
constexpr int MAXN = 100005;
template <size_t __length>
class my_bitset32 {
    unsigned _M_arr[(__length + 31) >> 5] = {0};
    static_assert(__length >= 1, "");
public:
    inline _GLIBCXX14_CONSTEXPR my_bitset32(unsigned long long val = 0) noexcept {
        if _GLIBCXX17_CONSTEXPR (__length >= 2) {
            _M_arr[1] = val & ((1ull << 32ull) - 1ull);
            _M_arr[0] = val >> 32ull;
        }
        else _M_arr[0] = val & ((1ull << 32ull) - 1ull);
    }
    class reference {
        size_t _M_pos;
        friend class my_bitset32<__length>;
        unsigned* ptr;
        inline _GLIBCXX_CONSTEXPR reference() {}
    public:
        reference(my_bitset32<__length>& b, size_t pos) noexcept {
            _M_pos = pos & 31;
            ptr = b._M_arr + (pos >> 5);
        }
        inline _GLIBCXX_CONSTEXPR operator bool() const noexcept { return (*(ptr) & (1 << _M_pos)) != 0; }
        inline _GLIBCXX_CONSTEXPR bool operator~() const noexcept { return (*(ptr) & (1 << _M_pos)) == 0; }
        inline _GLIBCXX14_CONSTEXPR reference& flip() noexcept {
            *ptr ^= (1 << _M_pos);
            return *this;
        }
        inline _GLIBCXX14_CONSTEXPR reference& operator=(bool v) noexcept {
            if (v) *ptr |= (1 << _M_pos);
            else *ptr &= ~(1 << _M_pos);
            return *this;
        }
        ~reference() {}
        inline _GLIBCXX14_CONSTEXPR reference(const reference&) = default;
    };
    friend class reference;
public:
#if __cplusplus > 202002L
    constexpr
#endif
    inline reference operator[](size_t index) { return reference(*this, index); }
    inline _GLIBCXX_CONSTEXPR bool operator[](size_t index) const { return (bool)reference(*this, index); }
    inline _GLIBCXX_CONSTEXPR size_t size() const noexcept { return __length; }
    inline size_t count() const noexcept {
        size_t ans = 0;
        for (size_t i = 0; i < ((__length + 31) >> 5); i++) ans += __builtin_popcount(_M_arr[i]);
        return ans;
    }
    inline bool test(size_t pos) const {
        if (pos >= size()) throw std::out_of_range("my_bitset32::test");
        return this->operator[](pos);
    }
    inline bool all() const noexcept {
        for (size_t i = 0; i < ((__length + 31) >> 5); i++) if (__builtin_popcount(_M_arr[i]) != 32) return false;
        return true;
    }
    inline bool none() const noexcept {
        for (size_t i = 0; i < ((__length + 31) >> 5); i++) if (__builtin_popcount(_M_arr[i]) != 0) return false;
        return true;
    }
    inline bool any() const noexcept {
        for (size_t i = 0; i < ((__length + 31) >> 5); i++) if (__builtin_popcount(_M_arr[i]) != 0) return true;
        return false;
    }
    inline _GLIBCXX14_CONSTEXPR my_bitset32<__length>& operator&=(const my_bitset32<__length>& other) noexcept {
        for (size_t i = 0; i < ((__length + 31) >> 5); i++) _M_arr[i] &= other._M_arr[i];
        return *this;
    }
    inline _GLIBCXX14_CONSTEXPR my_bitset32<__length>& operator|=(const my_bitset32<__length>& other) noexcept {
        for (size_t i = 0; i < ((__length + 31) >> 5); i++) _M_arr[i] |= other._M_arr[i];
        return *this;
    }
    inline _GLIBCXX14_CONSTEXPR my_bitset32<__length>& operator^=(const my_bitset32<__length>& other) noexcept {
        for (size_t i = 0; i < ((__length + 31) >> 5); i++) _M_arr[i] ^= other._M_arr[i];
        return *this;
    }
    inline _GLIBCXX14_CONSTEXPR my_bitset32<__length> operator~() const noexcept {
        my_bitset32<__length> res;
        for (size_t i = 0; i < ((__length + 31) >> 5); i++) res._M_arr[i] = ~_M_arr[i];
        for (size_t i = (__length & 31); i < 32; i++) res._M_arr[__length >> 5] &= ~(1 << i);
        return res;
    }
    inline void reset() { memset(_M_arr, 0, ((__length + 31) >> 5) * sizeof(unsigned)); }
};
std::vector<std::pair<int, int> > e[MAXN];
int d[MAXN];
my_bitset32<MAXN> vis;
char c;
constexpr size_t READ_MAXN = 1 << 16;
constexpr size_t READ_ARR_SIZE = READ_MAXN | 5;
char inbuf[READ_ARR_SIZE], outbuf[READ_ARR_SIZE];
char *curinpos = inbuf + READ_MAXN, *curoutpos = outbuf;
char *end_inbuf = inbuf + READ_MAXN, *end_outbuf = outbuf + READ_MAXN;
inline char gc() {
    if (curinpos == end_inbuf) {
        end_inbuf = inbuf + fread(inbuf, 1, READ_MAXN, stdin);
        curinpos = inbuf;
    }
    return *curinpos++;
}
inline void pc(char x) {
    if (curoutpos == end_outbuf) {
        fwrite(outbuf, 1, READ_MAXN, stdout);
        curoutpos = outbuf;
        end_outbuf = outbuf + READ_MAXN;
    }
    *curoutpos++ = x;
}
inline unsigned readuint() {
    unsigned eax(0);
    c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) eax = (eax << 3) + (eax << 1) + (c & 15), c = gc();
    return eax;
}
inline void putuint(unsigned x) {
    static char buf[15];
    static unsigned curpos;
    curpos = 0;
    do {
        buf[curpos++] = (x % 10) | 48;
        x /= 10;
    } while (x);
    while (curpos--) pc(buf[curpos]);
}
std::pair<unsigned, unsigned> heap[MAXN];
unsigned tot = 0;
inline void my_swap(unsigned& a, unsigned& b) { a ^= b ^= a ^= b; }
inline void my_swap(std::pair<unsigned, unsigned>& a, std::pair<unsigned, unsigned>& b) {
    my_swap(a.first, b.first);
    my_swap(a.second, b.second);
}
inline void __push(unsigned pos = tot) {
    while (pos > 1 && heap[pos] < heap[pos >> 1]) {
        my_swap(heap[pos], heap[pos >> 1]);
        pos >>= 1;
    }
}
inline void __adjust(unsigned pos = 1) {
    unsigned tar = pos << 1;
    while (tar <= tot) {
        if (tar < tot) tar = heap[tar] < heap[tar | 1] ? tar : (tar | 1);
        if (heap[pos] > heap[tar]) my_swap(heap[pos], heap[tar]);
        else break;
        pos = tar;
        tar = pos << 1;
    }
}
inline void push(const std::pair<unsigned, unsigned>& x) {
    heap[++tot] = x;
    __push();
}
inline void pop() {
    my_swap(heap[1], heap[tot--]);
    __adjust();
}
inline void add(int u, int v, int w) { e[u].emplace_back(v, w); }
inline void dij(unsigned s) {
    push(std::make_pair(0, s));
    memset(d, 0x3f, MAXN * sizeof(unsigned));
    vis.reset();
    d[s] = 0;
    while (tot) {
        int u = heap[1].second;
        pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : e[u]) if (d[v] > d[u] + w) {
            d[v] = d[u] + w;
            push(std::make_pair(d[v], v));
        }
    }
}
unsigned n, m, S;
void Read() {
    n = readuint(), m = readuint(), S = readuint();
    unsigned u, v, z;
    for (unsigned i = 1; i <= m; i++) {
        u = readuint(), v = readuint(), z = readuint();
        add(u, v, z);
    }
}
void Solve() {
    dij(S);
    for (unsigned i = 1; i <= n; i++) putuint(d[i] == 0x3f3f3f3f ? 2147483647 : d[i]), pc(' ');
}
int main() {
    Read();
    Solve();
    fwrite(outbuf, 1, curoutpos - outbuf, stdout);
    return 0;
}

by olegekei @ 2023-01-08 07:43:54

@MornHus

可以在元素存入堆里的时候取负数，这样大根堆就变成小根堆了，如果有需求的话取出来的时候再取一次负就行了