Bellman-ford

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,d[500001]; 
struct pio{
	int u,v,w;
}z[500001]; 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		d[i]=0x7fffffff;
	}d[s]=0;
	for(int i=1;i<=m;i++){
		cin>>z[i].u>>z[i].v>>z[i].w;
	}for(int i=1;i<=n;i++){
		bool flag=0;
		for(int j=1;j<=m;j++){
			int u=z[j].u,v=z[j].v,w=z[j].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				flag=true;
			}
		}if(!flag)break;
	}for(int i=1;i<=n;i++)cout<<d[i]<<" ";
	return 0;
}

Dijkstra

#include<bits/stdc++.h>
using namespace std;
int n,m,s,d[50001],vis[50001];
struct pio{
	int v,w;
};
vector<pio>z[50001]; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		z[u].push_back({v,w});
	}for(int i=1;i<=n;i++)d[i]=1e9;
	d[s]=0;
	for(int i=1;i<n;i++){
		int maxn=1e9,t;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&d[j]<maxn){
				maxn=d[j];
				t=j;
			}
		}vis[t]=1;
		for(int j=0;j<z[t].size();j++){
			int v=z[t][j].v,w=z[t][j].w;
			if(d[v]>d[t]+w){
				d[v]=d[t]+w;
			}
		}
	}for(int i=1;i<=n;i++)cout<<(d[i]==1e9?(1<<31)-1:d[i])<<" ";
	
	return 0;
}

floyd

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[101][101]; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]=1e9;
		}dp[i][i]=0;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		dp[u][v]=min(dp[u][v],w); 
		dp[v][u]=min(dp[u][v],w);
	}for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<dp[i][j]<<" ";
		}cout<<"\n";
	}
	return 0;
}

spfa

void spfa() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    memset(dist, INF, sizeof(dist));
    memset(inQueue, false, sizeof(inQueue));
    dist[1] = 0;
    pq.push({0, 1});
    inQueue[1] = true;
    while (!pq.empty()) {
        int u = pq.top().second; pq.pop();
        inQueue[u] = false;
        for (auto &e : edges[u]) {
            int v = e.first, w = e.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    pq.push({dist[v], v});
                    inQueue[v] = true;
                }
            }
        }
    }
}

Dijkstra优化

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,d[500001],vis[500001];
struct pio{
	int v,w;
};
struct node{
	int dis,u;
	bool operator>(const node& a) const { return dis > a.dis; }
};
vector<pio>z[500001]; 
priority_queue<node, vector<node>, greater<node> > q;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		z[u].push_back({v,w});
	}for(int i=1;i<=n;i++)d[i]=1e9;
	d[s]=0;
	q.push({0,s});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int j=0;j<z[u].size();j++){
			int v=z[u][j].v,w=z[u][j].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				q.push({d[v],v});
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<d[i]<<" ";
	
	return 0;
}

二分图

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,vis[10010],ans;
vector<int> z[10010];
bool dfs(int u,int c){
	vis[u]=c;
	c==1?a++:b++;
	for(int i=0;i<z[u].size();i++){
		if(vis[z[u][i]]==c||(!vis[z[u][i]]&&!dfs(z[u][i],3-c)))return false;
	}
	return true;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		int u,v;
		cin>>u>>v;
		z[u].push_back(v);
		z[v].push_back(u);
	}	
	for(int i = 1;i <= n;i++){
		if(!vis[i]&&!dfs(i,1)){
			cout<<"Impossible";
			return 0;
		}ans+=min(a,b);
		a=0;
		b=0;
	}
	cout<<ans<<endl;
}

二分图的最大匹配

#include<bits/stdc++.h>
using namespace std;
int n,m,e,vis[1001],match[1001],ans;
vector<int>z[1001];
bool dfs(int x){
	
	for(int i=0;i<z[x].size();i++){
		if(vis[z[x][i]]==0){
			vis[z[x][i]]=1;
			if(match[z[x][i]]==0||dfs(match[z[x][i]])){
				match[z[x][i]]=x;
				return true;
			}	
		}
	}return false;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>e;
	for(int i=1;i<=e;i++){
		int a,b;
		cin>>a>>b;
		z[a].push_back(b);
	}for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(dfs(i))ans++;
	}cout<<ans;
	return 0;
}