Template Gallery

Dijkstra

#include<cstdio>
#include<queue>
using namespace std;
 int cnt,n,m,s;
 int h[10010],d[10010];
struct Node{
    int d,id;}x;
struct Edge{int v,c,nt;}G[500010];
inline void adj(int x,int y,int c){ G[++cnt]=(Edge){y,c,h[x]}; h[x]=cnt; }
inline bool gmin(int &a,int b){return a>b?(a=b)|1:0;}
inline bool operator < (Node a,Node b){return a.d>b.d;}
void dij(int s){    
    priority_queue<Node> q;
    d[s]=0; q.push((Node){0,s});
    for(int u;!q.empty();){

        x=q.top();q.pop();
        if(d[u=x.id]<x.d) continue;
        for(int v,i=h[u];i;i=G[i].nt)
        if(gmin(d[v=G[i].v],d[u]+G[i].c)) q.push((Node){d[v],v});
    }   

} 
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;++i)d[i]=2147483647;
    for(int i=0;i<m;++i)
    {
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        adj(u,v,d);
    }
    dij(s);
    for(int i=1;i<=n;i++)
    printf("%d ",d[i]);
    return 0;
}

Kruskal

#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 10000;
const int MAXM = 100000;
struct Edge{
    int u;
    int v;
    int value;
    bool operator<(const Edge& x) const{
        return this -> value < x.value;
    }
};

Edge e[MAXM];
int father[MAXN];

int find_root(int x){
    return father[x] = (father[x] == x ? x : find_root(father[x]));
}

inline void union_set(int s1,int s2){
    father[find_root(s1)] = find_root(s2);
}

int main(){
    int Ans = 0;
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;++i) father[i] = i;
    for (int i=0;i<m;++i){
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].value);
        --e[i].u; --e[i].v;
    }
    sort(e+0,e+m);
    for (int i=0;i<m;++i){
        if (find_root(e[i].u) != find_root(e[i].v)){
            union_set(e[i].u,e[i].v);
            Ans += e[i].value;
        }
    }
    printf("%d\n",Ans);
}

Exgcd

inline int exgcd(int a,int b,int& x,int& y){
	if(b){
		int r=exgcd(b,a%b,y,x);
		y-=x*(a/b); return r;
	} else { x=1; y=0; return a; }
}