并查集

    class UnionFind{
        public:
            UnionFind(int n){
                count=n;
                parent.resize(n);
                member.resize(n);
                for(int i=0;i<n;++i){
                    parent[i]=i;
                    member[i]=1;
                }
            }
            void union(int i, int j){
                int parentI=find(i);
                int parentJ=find(j);
                if(parentI==parentJ) return ;
                if(size[parentI]>size[parentJ]){
                    parent[parentJ]=parentI;
                    member[parentI]+=member[parentJ];
                }else{
                    parent[parentI]=parentJ;
                    member[parentJ]+=member[parentI];
                }
                count--;
            }
            bool isConnected(int i, int j){
                int parentI=find(i);
                int parentJ=find(j);
                return parentI==parentJ;
            }
            int count(){
                return count;
            }    
        private:
            int find(int i){
                while(parent[i]!=i){
                    parent[i]=parent[parent[i]];
                    i=parent[i];
                }
                return i;
            }
        private:
            int count;
            vector<int> parent;
            vector<int> member;
        };

TrieTree

//前缀树(字典树)增删改查的实现
        //程序设计题目，如设计LRU缓存
        class TrieTree {
        private:
            struct TrieNode;
        public:
            TrieTree() {
                root = new TrieNode();
            }
        public:
            bool search(string& s) {
                if (s.empty() || s.length() == 0) return false;
                TrieNode* node = root;
                for (auto c : s) {
                    int index = c - 'a';
                    if ((node = node->map[index]) == nullptr)
                        return false;
                }
                return node->end != 0;
            }
            void insert(string& s) {
                if (s.empty() || s.length() == 0) return;
                TrieNode** node = &root;
                for (auto c : s) {
                    int index = c - 'a';
                    node=&((*node)->map[index]);
                    if ((*node) == nullptr) {
                        (*node) = new TrieNode();
                    }
                    (*node)->path++;
                }
                (*node)->end++;
            }
            void delStr(string& s) {
                if (s.empty() || s.length() == 0) return;
                TrieNode* node = root;
                if (search(s)) {
                    for (auto c : s) {
                        int index = c - 'a';
                        node = node->map[index];
                        if (node->path-- == 1) {
                            delete node;
                            node = nullptr;
                            return;
                        }
                    }
                    node->end--;
                }
            }
            int preQuery(string& s) {  //返回以s为前缀的串有几个
                if (s.empty() || s.length() == 0) return 0;
                TrieNode* node = root;
                for (auto c : s) {
                    int index = c - 'a';
                    if ((node = node->map[index]) == nullptr)
                        return 0;
                }
                return node->path;
            }
        private:
            TrieNode* root;
        private:
            struct TrieNode {
                int path;
                int end;
                vector<TrieNode*> map;
                TrieNode() :path(0), end(0) {
                    map.reserve(26);
                    for (auto itr : map)
                        itr = nullptr;
                }
            };
        };

DJ

#include<iostream>
#include<algorithm>
#include<queue>
#include<memory.h>
using namespace std;
struct edge{
    int to;
    int next;
    int w;
}edge[500010];
int cnt=0;
int head[100010];
int d[100010];
int vis[100010];
int n,m,u,v,w,s;
priority_queue<pair<int,int> >q;

inline void Add(int u,int v,int w){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
inline void DJ(int s){
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x])
        continue;
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            int z=edge[i].w;
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                if(!vis[y])
                {
                    q.push(make_pair(-d[y],y));
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        Add(u,v,w);
    }
    DJ(s);//s为起点
    for(int i=1;i<=n;i++){
        cout<<d[i]<<" ";
    }
}

质数欧拉筛

#include <algorithm>//std::remove_if
#include <numeric>//std::iota
std::vector<int> eratosthenes(int max){
    std::vector<int> vi(max+1);//0, 1, 2, ..., max
    std::iota(vi.begin(), vi.end(), 0);
    if(max>=2){
        int prime=2;
        while(prime*prime<=max){//2 to sqrt(max)
            for(size_t index=prime*2; index<vi.size(); index+=prime){
                vi[index]=0;//Rule out this number.
            }
            for(prime++; prime*prime<=max; prime++){
                if(vi[prime]>0){
                    break;//Jump to next non-zero.which is prime
                }
            }
        }
    }
    vi.erase(std::remove_if(vi.begin(), vi.end(), [](int i)->bool{
        return i<=1;
    }), vi.end());//Remove all zeros and the one.
    return vi;
}