图论算法学习笔记

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;
}