dijk template

#include<iostream>
#include<climits>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
struct Node{
	int to,far;
};
std::vector<ll>dijk(std::vector<std::vector<Node>>G,int n,int start){
	std::vector<ll>dist(n+1,INT_MAX);
	std::vector<bool>vis(n+1,0);
	std::priority_queue<std::pair<ll,ll>,std::vector<std::pair<ll,ll>>,std::greater<std::pair<ll,ll>>>q;
	q.push(std::make_pair(0,start));
	dist[start]=0;
	while(q.size()){
		ll from=q.top().second;
		q.pop();
		if(vis[from]){
			continue;
		}
		vis[from]=1;
		for(auto i:G[from]){
			if(dist[i.to]>dist[from]+i.far){
				dist[i.to]=dist[from]+i.far;
				q.push(std::make_pair(dist[i.to],i.to));
			}
		}
	}
	return dist;
}

ybt 1376

floyd

#include<iostream>
#include<climits>
#include<cstring>
#include<queue>
#include<vector>
#define infinity 0x3f3f3f3f
#define N 105
int n,m,G[N][N],dist[N][N];
int main(){
	memset(dist,infinity,sizeof(dist));
	std::cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c;
		std::cin>>a>>b>>c;
		G[a][b]=G[b][a]=c;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j){
				G[i][j]=0;
			}else if(G[i][j]){
				dist[i][j]=G[i][j];
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				if(dist[j][k]>dist[j][i]+dist[i][k]){
					dist[j][k]=dist[j][i]+dist[i][k];
				}
			}
		}
	}
	int res=INT_MIN;
	for(int i=1;i<=n;i++){
		if(dist[1][i]==infinity){
			std::cout<<-1;
			return 0;
		}else{
			res=std::max(res,dist[1][i]);
		}
	}
	std::cout<<res;
}

dijk

#include<iostream>
#include<climits>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
struct Node{
	int to,far;
};
std::vector<ll>dijk(std::vector<std::vector<Node>>G,int n,int start){
	std::vector<ll>dist(n+1,INT_MAX);
	std::vector<bool>vis(n+1,0);
	std::priority_queue<std::pair<ll,ll>,std::vector<std::pair<ll,ll>>,std::greater<std::pair<ll,ll>>>q;
	q.push(std::make_pair(0,start));
	dist[start]=0;
	while(q.size()){
		ll from=q.top().second;
		q.pop();
		if(vis[from]){
			continue;
		}
		vis[from]=1;
		for(auto i:G[from]){
			if(dist[i.to]>dist[from]+i.far){
				dist[i.to]=dist[from]+i.far;
				q.push(std::make_pair(dist[i.to],i.to));
			}
		}
	}
	return dist;
}
int main(){
	int n,m;
	std::cin>>n>>m;
	std::vector<std::vector<Node>>G(n+1);
	for(int i=0;i<m;i++){
		int from,to,far;
		std::cin>>from>>to>>far;
		G[from].push_back(Node{to,far});
		G[to].push_back(Node{from, far});
	}
	std::vector<ll>f=dijk(G,n,1);
	ll res=INT_MIN;
	for(int i=1;i<=n;i++){
		res=std::max(res,f[i]);
	}
	if(res==INT_MIN)std::cout<<-1;
	else std::cout<<res;
}

luogu p1828

堆优化dijk

#include<iostream>
#include<climits>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
#define N 105
struct Node{
	int to,far;
};
int cnt[N];
std::vector<ll>dijk(std::vector<std::vector<Node>>G,int n,int start){
	std::vector<ll>dist(n+1,INT_MAX);
	std::vector<bool>vis(n+1,0);
	std::priority_queue<std::pair<ll,ll>,std::vector<std::pair<ll,ll>>,std::greater<std::pair<ll,ll>>>q;
	q.push(std::make_pair(0,start));
	dist[start]=0;
	while(q.size()){
		ll from=q.top().second;
		q.pop();
		if(vis[from]){
			continue;
		}
		vis[from]=1;
		for(auto i:G[from]){
			if(dist[i.to]>dist[from]+i.far){
				dist[i.to]=dist[from]+i.far;
				q.push(std::make_pair(dist[i.to],i.to));
			}
		}
	}
	return dist;
}
int main(){
	int n,p,c;
	std::cin>>n>>p>>c;
	std::vector<std::vector<Node>>G(p+1);
	for(int i=1;i<=n;i++){
		int x;
		std::cin>>x;
		cnt[x]++;
	}
	for(int i=1;i<=c;i++){
		int u,v,w;
		std::cin>>u>>v>>w;
		G[u].push_back(Node{v,w});
		G[v].push_back(Node{u,w});
	}
	int minn=1<<30;
	for(int i=1;i<=p;i++){
		std::vector<ll>dist=dijk(G,p,i);
		int sum=0;
		for(int j=1;j<=p;j++){
			sum+=(dist[j]*cnt[j]);
		}
		minn=std::min(sum,minn);
	}
	std::cout<<minn;
}

luogu b3647

floyd

#include<iostream>
#define infinity 0x3f3f3f3f
#define N 105
int G[N][N];
int main(){
	int n,m;
	std::cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j){
				G[i][j]=0;
			}else{
				G[i][j]=infinity;
			}
		}
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		std::cin>>u>>v>>w;
		G[u][v]=std::min(G[u][v],w);
		G[v][u]=std::min(G[v][u],w);
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(G[i][j]>G[i][k]+G[k][j]){
					G[i][j]=G[i][k]+G[k][j];
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			std::cout<<G[i][j]<<' ';
		}
		std::cout<<std::endl;
	}
}